一道很经典的DP，状态转移方程为：f[i,j,k]=max{f[i-1,j,k],f[i-1,j-1,k-(p[i]-d[i])]+p[i]+d[i]}。其中f[i,j,k]表示在前i个候选人中选择j个人,并且辩控差为k时的最大辩控和。另外用path[i,j,k]来记录路径，表示当前方案下选择的最后一个人。详细见代码：
#include<iostream>
#include<stack>
using namespace std;
int n,m,test;
int p[205],d[205];
int f[205][25][805];
int path[205][25][805];
int main()
{
test=0;
while(scanf("%d%d",&n,&m)!=EOF&&(m||n))
{
int i,j,k;
for(i=1;i<=n;i++)
scanf("%d%d",&p[i],&d[i]);
int mid=m*20;
memset(f,-1,sizeof(f));
memset(path,-1,sizeof(path));
for(i=0;i<=n;i++) f[i][0][mid]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m&&j<=i;j++)
for(k=0;k<=2*mid;k++)
{
f[i][j][k]=f[i-1][j][k];
path[i][j][k]=path[i-1][j][k];
if(k>=p[i]-d[i]&&k-(p[i]-d[i])<=2*mid
&&f[i-1][j-1][k-(p[i]-d[i])]!=-1
&&f[i][j][k]<=f[i-1][j-1][k-(p[i]-d[i])]+p[i]+d[i])
{
f[i][j][k]=f[i-1][j-1][k-(p[i]-d[i])]+p[i]+d[i];
path[i][j][k]=i;
}
}
i=0;
int conc;
while(i<=mid)
{
if(f[n][m][mid+i]!=-1||f[n][m][mid-i]!=-1)
break;
i++;
}
if(f[n][m][mid+i]>f[n][m][mid-i])
conc=mid+i;
else conc=mid-i;
int prose=0,def=0;
stack<int> ss;
i=path[n][m][conc];
j=m;
while(i!=-1)
{
prose+=p[i];
def+=d[i];
ss.push(i);
j=j-1;
conc-=(p[i]-d[i]);
i=path[i-1][j][conc];
}
printf("Jury #%d\n",++test);
printf("Best jury has value %d for prosecution and value %d for defence:\n",prose,def);
while(!ss.empty())
{
printf(" %d",ss.top());
ss.pop();
}
printf("\n\n");
}
return 0;
}
posted on 2010-08-09 01:16
wuxu 阅读(271)
评论(0) 编辑 收藏 引用 所属分类:
动态规划