CodeForces 688E-The Values You Can Make

时间：2023-12-06 16:57:44

题意:
　　给出n,k,分别代表硬币的数量与巧克力的价格，n个整数c1,c2,...ci...cn(ci代表第i块硬币的值);你可以从n块硬币中拿出金额恰好为k的硬币数并将其中的任意两块硬币组合得到一个数，将其保存下来(0和输入的n个数的值也必须被保存),最后将这些数按升序排列输出.

分析：
　　可以采用dp的递推方法,从1到n,dp[i][j]代表通过前i个元素和为i,能否组合出j.

代码如下:

 #include <cstdio>

 #include <iostream>

 #include <ctime>

 #include <vector>

 #include <cmath>

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 const int maxn = 1e5+;

 int a[maxn],n,p;

 int dp[][],tmp[];

 vector<int>ret;

 int main()

 {

     int i, j, k;

     while(scanf("%d%d",&n, &p)==)

     {

         ret.clear();

         for(i = ; i <= n; i++ )

           scanf("%d", &a[i]);

         sort(a+, a++n);

         dp[][] = ;   //dp[i][j]代表通过前i个元素和为i,能否组合出j

         for(i = ; i <= n; i++ )

           for(j = p; j >= a[i]; j-- )

             for(k = ; k + a[i] <= p; k++ )

                 if(dp[j-a[i]][k])

                     dp[j][k] = dp[j][k+a[i]] = ;

         for(i = ; i <= p; i++ )

           if(dp[p][i])

             ret.push_back(i);

         printf("%d\n", ret.size());

         for(i = ; i < ret.size()-; i++ )

           printf("%d ", ret[i]);

         printf("%d\n", ret[ret.size()-]);

     }

     return ;

 }

相关文章