其实正解就是\(dfs+DP\)
但是因为自己写的不够好,再加上没有判断好\(DP\)的复杂度,导致\(T\)了好几次。错点还是有的:
- 1.多测不清空,爆零两行泪
- 2.0的情况不行,不要以为\(i\)从1开始枚举就可以了。万一之后枚举到的数只有1个1,且这个1对应的位置是被标记删除的位置,又出现了1。
题解里还有一种神奇的优化\(DP\),的方法,但是加上就会莫名\(RE\)。
学习\(dfs\)的写法:
#include#include #include using namespace std;int n,m,a[55],ans,sumt;bool book[2005],sum[50005];/*void print(){ memset(sum,0,sizeof(sum)); int anst=0; for(int i=1;i<(1<<(n+1));i++) { int ansm=0; for(int j=1;j<=n;j++) if(i&(1<<(j-1))&&!book[j]) ansm+=a[j]; if(!sum[ansm]&&ansm!=0) ++anst; sum[ansm]=1; } ans=max(ans,anst);}*/void print(){ memset(sum,0,sizeof(sum)); int anst=0; sum[0]=1; for(int i=1;i<=n;i++) if(!book[i]) { for(int j=sumt-a[i];j>=0;j--) { if(sum[j]) { if(!sum[j+a[i]]) ++anst; sum[j+a[i]]=1; } } } ans=max(ans,anst);}void dfs(int t,int u){ if(t>=m) { print(); return ;} if(u>n) return ; dfs(t,u+1); book[u]=1; dfs(t+1,u+1); book[u]=0;/* for(int i=1;i<=n;i++) if(!book[i]) { book[i]=1; dfs(t+1); book[i]=0; }*/}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]),sumt+=a[i]; if(m==0) { print(); printf("%d\n",ans); return 0; } if(m==1) { for(int i=1;i<=n;i++) { book[i]=1; print(); book[i]=0; } printf("%d\n",ans); return 0; } dfs(0,1); printf("%d\n",ans); return 0;}