先写了个两层搜索，后来又参考题解改了个搜索+动态规划。
题解：https://www.luogu.org/blog/yeyangrui/solution-p1441
60分搜索：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include<iostream> #include<algorithm> #include<cstring> #define NINF 0x80000000 using namespace std; int n,m; bool mass[2005]; int weight[25]; bool visited[25]; void dfs(int pos,int num){ if(pos==n+1)return; if(visited[pos]){ dfs(pos+1,num); return; } mass[num+weight[pos]]=true; dfs(pos+1,num+weight[pos]); mass[num]=true; dfs(pos+1,num); } int getMassCounts(){ memset(mass,false,sizeof(mass)); dfs(1,0); int cnter=0; for(int i=1;i<=n*100;i++)if(mass[i])cnter++; return cnter; } int genCombination(int pos,int num){ if(num==m)return getMassCounts(); if(pos>n)return NINF; int maxC=NINF; visited[pos]=true; maxC=max(maxC,genCombination(pos+1,num+1)); visited[pos]=false; maxC=max(maxC,genCombination(pos+1,num)); return maxC; } int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++)cin>>weight[i]; cout<<genCombination(1,0); } |
100分动规：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include<iostream> #include<algorithm> #include<cstring> #define NINF 0x80000000 using namespace std; int n,m; int f[2005]; int weight[25]; bool visited[25]; int getMassCounts(){ memset(f,0,sizeof(f)); f[0]=1; for(int i=1;i<=n;i++){ if(visited[i])continue; for(int j=2000;j>=0;j--){ if(j+weight[i]<=2000&&f[j]!=0)f[j+weight[i]]=1; } } int cnter=0; for(int i=1;i<=2000;i++)if(f[i])cnter++; return cnter; } int genCombination(int pos,int num){ if(num==m)return getMassCounts(); if(pos>n)return NINF; int maxC=NINF; visited[pos]=true; maxC=max(maxC,genCombination(pos+1,num+1)); visited[pos]=false; maxC=max(maxC,genCombination(pos+1,num)); return maxC; } int main(){ ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++)cin>>weight[i]; cout<<genCombination(1,0); } |