正题
题目链接:/problem?id=1015
题目大意
每个人有A值和B值，要求选M个人，使这M个人的|SumA−SumB||SumA−SumB|最小。
解题思路
我们用SumA−SumBSumA−SumB作为原本的价格，然后用fi,jfi,j表示已经选了i个人，SumA−SumBSumA−SumB为j时的情况，然后用dd数组统计每个状态是从哪个转移过来的，然后进行dp。
注意：c++没有负数下标，所以要加一个
code
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n,m,f[31][801],a[811],b[811],d[31][801],x,wr[31],t;bool write(int x,int y,int z)//判断路径是否正确{while(x&&d[x][y]!=z){y-=a[d[x][y]]-b[d[x][y]];x--;}return !x;}int main(){n=1;while(scanf("%d%d",&n,&m)&&n!=0&&m!=0){memset(f,-1,sizeof(f));memset(d,0,sizeof(d));f[0][m*20]=0;for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);}for(int i=1;i<=m;i++)for(int j=0;j<=m*40;j++)if(f[i-1][j]>=0)//有这个状态for(int k=1;k<=n;k++){if(f[i][j+a[k]-b[k]]<f[i-1][j]+a[k]+b[k]&&write(i-1,j,k))//是否可以转移{f[i][j+a[k]-b[k]]=f[i-1][j]+a[k]+b[k];d[i][j+a[k]-b[k]]=k;}}printf("Jury #%d\n",++t);int k1=0;while(k1<=m*20&&f[m][m*20+k1]<0&&f[m][m*20-k1]<0) k1++;//寻找答案int ans=f[m][m*20+k1]>f[m][m*20-k1]?m*20+k1:m*20-k1;//计算正负printf("Best jury has value %d for prosecution and value %d for defence:\n",(ans+f[m][ans]-m*20)>>1,(f[m][ans]-ans+m*20)>>1);//输出for (int i=1,j=m,k=ans;i<=m;i++){wr[i]=d[j][k];k-=a[d[j][k]]-b[d[j][k]];j--;}//记录方案sort(wr+1,wr+1+m);//按顺序for (int i=1;i<=m;i++) printf(" %d",wr[i]);printf("\n\n");}}
