CF GYM 10499J Healthy Recipes（DP）

题目链接

题意观察样例与提示即可。

挺水的 DP 题，DP 刷的比较少。。

#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
long long a[105], dp[10005];

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        memset(dp, 0, sizeof(dp));
        int n, m, k;
        dp[0] =1;
        scanf("%d %d %d", &n, &m, &k);
        for(int i = 1; i <= n; i++){
            scanf("%I64d", &a[i]);
        }
        for(int i = 1; i <= n; i++){
            for(int j = m; j >= a[i]; j--){
                dp[j] += dp[j-a[i]];
            }
            if(dp[m] >= k)
                break;
        }
        if(dp[m] >= k) cout << "ENOUGH" << endl;
        else cout << dp[m] << endl;
    }
    return 0;
}