POJ 1015 Jury Compromise

时间:2021-10-23 18:25:08

感觉此题略难。。。。。。

背包问题。据说有一种二维DP的写法是错的。亲测,背包做法无误。

dp[i][j][k]表示前i个物品,选择j个,差值为k的情况下获得的最大总和

dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-1][k-差]+和) 即第i个物品用或者不用。

DP完成之后,在表中寻找一下最优解即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std; struct Path
{
// int a,b,c;
int w;
} path[+][+][+];
int dp[+][+][+];
int p[+],d[+];
int n,m;
stack<int>S;
int Z=; int main()
{
int Case=;
while(~scanf("%d%d",&n,&m))
{
if(!n&&!m) break; for(int i=; i<=n; i++) scanf("%d%d",&p[i],&d[i]);
memset(dp,-,sizeof dp);
dp[][][Z]=; for(int i=; i<=n; i++)
for(int j=; j<=m; j++)
for(int k=; k<=*Z; k++)
path[i][j][k].w=-; for(int i=; i<=n; i++)
{
for(int j=; j<=m; j++)
{
for(int k=Z*; k-(p[i]-d[i])>=; k--)
{
if(dp[i-][j][k]!=-)
{
dp[i][j][k]=dp[i-][j][k];
path[i][j][k].w=;
} if(j>=&&dp[i-][j-][k-(p[i]-d[i])]!=-)
{
if(dp[i-][j-][k-(p[i]-d[i])]+p[i]+d[i]>dp[i][j][k])
{
dp[i][j][k]=dp[i-][j-][k-(p[i]-d[i])]+p[i]+d[i];
path[i][j][k].w=;
}
}
}
}
} int posa,posb,posc;
int Max=-;
for(int i=; i<=Z; i++)
{
for(int j=; j<=n; j++)
if(dp[j][m][Z+i]>Max&&path[j][m][Z+i].w==)
Max=dp[j][m][Z+i],posa=j,posb=m,posc=Z+i;
for(int j=; j<=n; j++)
if(dp[j][m][Z-i]>Max&&path[j][m][Z-i].w==)
Max=dp[j][m][Z-i],posa=j,posb=m,posc=Z-i;
if(Max!=-) break;
} while(!S.empty()) S.pop(); int ans1,ans2;
ans1=(posc-Z+dp[posa][posb][posc])/;
ans2=ans1-(posc-Z); while()
{
if(path[posa][posb][posc].w==-) break;
if(path[posa][posb][posc].w!=-)
{
int Newa,Newb,Newc;
if(path[posa][posb][posc].w==)
{
S.push(posa);
Newa=posa-;
Newb=posb-;
Newc=posc-(p[posa]-d[posa]);
}
else
{
Newa=posa-;
Newb=posb;
Newc=posc;
}
posa=Newa;
posb=Newb;
posc=Newc;
}
} printf("Jury #%d\n",Case++);
printf("Best jury has value %d for prosecution and value %d for defence:\n",ans1,ans2);
while(!S.empty())
{
printf(" %d",S.top());
S.pop();
}
printf("\n\n"); }
return ;
}