偷的代码,两份代码都是可以A的,但是很奇怪,没case之间没输出空行能过。
更奇怪的是,这组数据一直过不了
9 6
6 2
16 10
4 9
19 8
17 12
4 7
10 2
2 14
5 18
答案:
1 2 3 4 6 9
一开始尝试,把n放在外层,m的枚举放在里层的for也没过
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <set> #include <algorithm> #include <vector> #include <string> using namespace std; #define fix 400 #define N 205 int dp[23][1000]; int path[24][1000]; int a[N],b[N],out[N]; int n,m; int main () { int ncase=1; while(scanf("%d%d",&n,&m)!=EOF) { int u,v; for(int i=1;i<=n;++i) { scanf("%d%d",&u,&v); a[i]=u-v; b[i]=u+v; } memset(dp,-1,sizeof(dp)); dp[0][fix]=0; for(int j=1;j<=m;++j) for(int k=0;k<=2*fix;++k) if(dp[j-1][k]>=0) { for(int i=1;i<=n;++i) if(dp[j][k+a[i]]<dp[j-1][k]+b[i]) { bool flag=true; for(int z=k,t=j-1;z>=0 && t>0;--t) { if(path[t][z]==i) { flag=false; break; } z-=a[path[t][z]]; } if(flag) { dp[j][k+a[i]]=dp[j-1][k]+b[i]; path[j][k+a[i]]=i; } } } int ans; for(int i=0;i<=fix;++i) if(dp[m][fix+i]>=0 || dp[m][fix-i]>=0) { if(dp[m][fix+i]>=0) ans=fix+i; if(dp[m][fix-i]>dp[m][ans]) ans=fix-i; break; } int uu=0,vv=0; for(int i=m,pos=ans;i>=1;--i) { int index=path[i][pos]; uu+=(a[index]+b[index])/2; vv+=(b[index]-a[index])/2; out[i]=index; pos-=a[index]; } printf("Jury #%d\n",ncase++); printf("Best jury has value %d for prosecution and value %d for defence:\n",uu,vv); sort(out+1,out+1+m); for(int i=1;i<=m;++i) printf(" %d",out[i]); printf("\n"); } return 0; } /*int a[N],b[N],out[N]; int n,m; int dp[fix*3][25]; int idx[fix*3][25]; int main () { int ncase=1; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0 && m==0) break; int u,v; for(int i=1;i<=n;++i) { scanf("%d%d",&u,&v); a[i]=u-v; b[i]=u+v; } memset(dp,-1,sizeof(dp)); dp[fix][0]=0; for(int i=1;i<=m;++i) for(int j=0;j<=fix*2;++j) if(dp[j][i-1]>=0) { for(int k=1;k<=n;++k) { if(dp[j+a[k]][i]<dp[j][i-1]+b[k]) { bool f=true; for(int z=j,t=i-1;z>=0 && t>=0;z-=a[idx[z][t]],--t) { if(idx[z][t]==k) { f=false; break; } } if(f) //if(select(i-1,j,k,a)) { dp[j+a[k]][i]=dp[j][i-1]+b[k]; idx[j+a[k]][i]=k; } } } } int ans; for(int i=0;i<=fix;++i) if(dp[fix+i][m]!=-1 && dp[fix-i][m]!=-1) { ans=fix+i; if(dp[fix+i][m]<dp[fix-i][m]) ans=fix-i; break; } else if(dp[fix+i][m]!=-1) { ans=fix+i; break; } else if(dp[fix-i][m]!=-1) { ans=fix-i; break; } printf("Jury #%d\n",ncase++); int uu=0,vv=0; for(int i=m,pos=ans;i>=1;--i) { int index=idx[pos][i]; uu+=(a[index]+b[index])/2; vv+=(b[index]-a[index])/2; out[i]=index; pos-=a[index]; } printf("Best jury has value %d for prosecution and value %d for defence:\n",uu,vv); sort(out+1,out+1+m); for(int i=1;i<=m;++i) printf(" %d",out[i]); printf("\n"); } return 0; }*/
把n放外层,m放里层的for,然后逆序枚举,过不了样例,仔细想了,因为确定了第m个,再确定第i(i<m)个的时候,无法确定更新了是否能得到更大的P[X]+D[X]
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <set> #include <algorithm> #include <vector> #include <string> using namespace std; #define fix 400 #define N 205 int a[N],b[N],out[N]; int dp[25][fix*3]; int idx[25][fix*3]; int n,m; int main () { int ncase=1; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0 && m==0) break; int u,v; for(int i=1;i<=n;++i) { scanf("%d%d",&u,&v); a[i]=u-v; b[i]=u+v; } memset(dp,-1,sizeof(dp)); dp[0][fix]=0; for(int i=1;i<=n;++i) { for(int t=m;t>=1;--t) for(int j=0;j<=fix*2;++j) if(dp[t-1][j]>=0 && dp[t][j+a[i]]<dp[t-1][j]+b[i]) { // judge bool flag=true; for(int z=j+a[i],tt=t;z<=fix*2 && tt<=m ;++tt) { if(idx[tt][z]==i) { flag=false; break; } z+=a[idx[tt][z]]; } if(flag) { dp[t][j+a[i]]=dp[t-1][j]+b[i]; idx[t][j+a[i]]=i; } } } int ans=0; for(int i=0;i<=fix;++i) if(dp[m][fix+i]>=0 || dp[m][fix-i]>=0) { if(dp[m][fix+i]>=0) ans=fix+i; if(dp[m][ans]<dp[m][fix-i]) ans=fix-i; break; } int uu=0,vv=0; for(int i=m,pos=ans;i>=1;--i) { int index=idx[i][pos]; uu+=(a[index]+b[index])/2; vv+=(b[index]-a[index])/2; out[i]=index; pos-=a[index]; } printf("Jury #%d\n",ncase++); printf("Best jury has value %d for prosecution and value %d for defence:\n",uu,vv); sort(out+1,out+1+m); for(int i=1;i<=m;++i) printf(" %d",out[i]); printf("\n"); } return 0; }