题解 | 神奇的口袋

#include <iostream>
#include<vector>
using namespace std;

int main() {
    int N;
    while (cin >>N) { // 注意 while 处理多个 case
        vector<vector<int>>dp(N+1,vector<int>(41,0));
        vector<int>vec(N+1);
        for(int i=1;i<=N;i++){
            cin>>vec[i];
        }
	 	 //二维动态规划
        // dp[n][40]=dp[n-1][40]+dp[n-1][40-vec[n]]
        for(int i=1;i<=N;i++){
            if(vec[i]==40)dp[i][40]=1;
        }
        dp[0][0]=1;
        for(int i=1;i<=N;i++){
            for(int j=0;j<=40;j++){
                if(j>=vec[i])dp[i][j]=dp[i-1][j]+dp[i-1][j-vec[i]];
                else dp[i][j]=dp[i-1][j];
            }
        }
        cout<<dp[N][40];
    }
}
// 64 位输出请用 printf("%lld")