CodeForces 688E-The Values You Can Make

题意:
  给出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 ;
}
上一篇:用Bootstrap做一个历史朝代表


下一篇:使用bootstrap做一个响应式的页面