Problem
就是说给你n个硬币，然后让你支付m的货物，让你求出那些硬币是必须的。。、
n<=200,m<=10000
这个数据范围，如果枚举每个硬币，然后计算的化，绝对会悲剧，
怎么办呢，我注意到要尽量利用计算的信息，
设L[x]表是1->x-1这些硬币能支付的钱的集合。
R[x]是x+1->n这些硬币能支付的钱的集合。
使用布尔数组或者bitset来表示，那么可以在O(nm)算出这些数。。
然后检查第x个是不是必须的就很方便了，可以在O(m)完成。。
Code：

#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<cstring>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;const int maxm=10000+1,maxn=200;int m,n;int A[maxn];struct Coins{ bool C[maxm]; int M; Coins(){memset(C,0,sizeof(C));M=0;C[0]=true;} void put(int x) { for(int i=M;i>=0;–i) if(C[i]&&i+x<=m) C[i+x]=true; M+=x;M=min(M,m); } void operator=(const Coins&o) { memmove(C,o.C,sizeof(C)); M=o.M; } bool& operator[](int v){return C[v];}};Coins L[maxn],R[maxn];void init(){ cin>>n>>m; rep(i,n) cin>>A[i];}void solve(){ Coins tmp; for(int i=0;i<n;i++) { L[i]=tmp; tmp.put(A[i]); } tmp=Coins(); for(int i=n-1;i>=0;–i) { R[i]=tmp; tmp.put(A[i]); } vector<int> ans; for(int i=0;i<n;i++) { bool ok=false; for(int x=0;x<=m;x++) if(L[i][x]&&R[i][m-x]) { ok=true;break; } if(!ok) ans.push_back(A[i]); } cout<<ans.size()<<endl; rep(i,ans.size()) cout<<ans[i]<<" ";}int main(){ //freopen("in","r",stdin); init(); solve();}

本高亮代码使用codeHl生成，查看详情