#include <iostream>
using namespace std;
#define max(a,b) (a>b?a:b)
const int N=810;
const int oo=-(1<<30);
int dp[210][21][N],d[210],p[210],q[210],end;
//q[]是存最后的选择了谁的,end是q[]的大小

void dfs(int i,int j,int k)//递归寻找选择了谁,存到q[]里,,
{
	if(i==0||j==0)
		return;
	if(dp[i-1][j][k]<dp[i-1][j-1][k-d[i]+p[i]]+d[i]+p[i])
	{
		q[end++]=i;
		dfs(i-1,j-1,k-d[i]+p[i]);
	}
	else
		dfs(i-1,j,k);
}
int main()
{
	int n,m,num=1;//num是用来输出#后边那个数字,,
	while(scanf("%d%d",&n,&m)&&n)
	{
		int i,j,k;
		for(i=1;i<=n;i++)
			scanf("%d%d",&p[i],&d[i]);
		for(i=0;i<=n;i++)//负初值
			for(j=0;j<=m;j++)
				for(k=0;k<=800;k++)
					if(j==0&&k==400)
						dp[i][j][k]=0;
					else
						dp[i][j][k]=oo;
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				for(k=1;k<=800;k++)
					if(k>=d[i]-p[i]&&k-d[i]+p[i]<=800)
						dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-1][k-d[i]+p[i]]+d[i]+p[i]);
			}//这就是我的dp方程,,感觉没问题啊,,,就一个01背包,,
		int ansk;//下面寻找最佳答案,,
		for(k=0;;k++)
		{
			if(dp[n][m][k+400]>=0&&dp[n][m][k+400]>=dp[n][m][400-k])
			{
				ansk=400+k;
				break;
			}
			else if(dp[n][m][400-k]>=0)
			{
				ansk=400-k;
				break;
			}
		}
		end=0;
		dfs(n,m,ansk);//递归
		int px=0,dx=0;
		for(i=0;i<end;i++)
			px+=p[q[i]],dx+=d[q[i]];//计算,,
		printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n",num++,px,dx);
		for(i=end-1;i>=0;i--)
			printf(" %d",q[i]);
		printf("\n\n");
	}
	return 0;
}

• 晕,,,过啦,,,笑死了,,,,dp时k竟然稀里糊涂的从1开始的,,,改成从0开始就过了,,哈哈哈哈,,,哈哈哈哈 (0) yy17yy 2011-01-26 10:27:01