题解 | #小Q的歌单#

1. 01背包问题

#include<bits/stdc++.h>
using namespace std;
const int mod =1000000007;
//背包问题的演变（只不过是两种物品，每种物品得）
vector<vector<int>> dp(1001,vector<int>(210,0));
int main(){

    int k, a,x,b,y;
    cin>>k;
    cin>>a>>x>>b>>y;
    int length = x+y;

    int len[210];
    for(int i = 1; i<= x;i++){
        len[i] = a;
    }
    for(int i = x +1; i<=length;i++){
        len[i] = b;
    }
    dp[0][0] = 1;//必要的初始条件，否则加出来永远是0
    for(int j = 1;j <=length; j++){
        for(int i = 0; i<=k; i++){
            if(i>=len[j]){
                dp[i][j] = (dp[i][j-1] + dp[i-len[j]][j-1])%mod;
            }else{
                dp[i][j] = (dp[i][j-1])%mod;
            }
        }

    }

    cout<<dp[k][length]<<endl;


    return 0;
}