链接：https://vjudge.net/problem/OpenJ_Bailian-4120
思路：首先分析，如果一种硬币必须，那么除开这种硬币，就没法达到预期x的值，所以想着遍历所有硬币，除开当前硬币进行dp，如果能得到最后x值则不是必须的，反之为必须的，这样的复杂度为O（mn^2），超时，及时加了优化也不行。后来发现，其实很多部分重新计算了，不如计算出每种钱j选法的次数g[j]，如果g[x]=0，那么当前硬币就是必需的。这种方法的复杂度O（mn）
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 201;
int a[maxn];
int f[10001];
int g[10001];
int n,x,t=0;
int b[maxn];
int main(){
scanf("%d%d",&n,&x);
memset(b,0,sizeof(b));
for(int i=0;i<n;++i)scanf("%d",&a[i]);
f[0] = 1;
for(int i=0;i<n;++i){
for(int j=x;j>=a[i];--j){
f[j] += f[j-a[i]];
}
}
for(int i=0;i<n;i++){
memset(g,0,sizeof(g));
for(int j=0;j<=x;j++){
if(j-a[i]>=0){
g[j] = f[j] - g[j-a[i]];
}
else g[j] = f[j];
}
if(g[x]==0){
b[i] = 1;
t++;
}
}
printf("%d\n",t);
t = 0;
for(int i=0;i<n;i++){
if(b[i]==1){
if(t){
printf(" ");
}
printf("%d",a[i]);
t++;
}
}
printf("\n");
return 0;
}
