UVA323 Jury Compromise 题解

题目简述：给定n个元素，其有a和b两种属性，从中选m个元素，使得属性a之和与属性b之和的差值最小，满足上述条件后再保证属性a之和与属性b之和的和最大。要求输出方案。

分析：先不考输出方案，就是个简单的dp题。因为数据范围较小，可以多开几个维度，先考虑一维f[i]表示前i个元素中挑的最小差值，然而发现不能递推，于是增加第二维表示差值，这样，f[i][j]表示从i个元素中挑出差值j是否可能。然后，考虑到挑选元素个数的限制，再增加一维表示元素个数，这样,f[i][j][k]表示从前i个元素挑k个元素达到j差值的最大和，那么状态的问题就解决了，方程很好写，这里不写了。考虑输出方案，需要开一个三维bool数组记录第i个元素取或不取的决策，这里可以状态压缩一下，具体见代码。还有一些细节，差值可能为负数，需要加400平移到正，dp可以滚动优化去掉一维空间，最后的时间复杂度为O(800*n*m)，空间复杂度为O(800*n)。

代码：

#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
const int N=200+5,M=20+5,MAX=800+5;
int n,m;
int a[N],b[N];
int f1[MAX][M],f2[MAX][M];
int p[N][MAX];
void dp()
{
	for (int i=1;i<=n;i++)
	  {
	  	 for (int j=0;j<=800;j++)
	       for (int k=0;k<=m;k++)
	        {
	           f2[j][k]=f1[j][k];
	           int d=a[i]-b[i];
	           if (j-d<0||j-d>800||k-1<0||f1[j-d][k-1]==-1) continue;
	           if (f1[j-d][k-1]+a[i]+b[i]<=f2[j][k]) continue;
	           f2[j][k]=f1[j-d][k-1]+a[i]+b[i];
	           p[i][j]=p[i][j]|(1<<k);
		    }
	     for (int j=0;j<=800;j++)
	       for (int k=0;k<=m;k++) 
	         f1[j][k]=f2[j][k];
	  }
}
int get()
{
	for (int d=0;d<=400;d++)
	  {
	     bool p1=f2[400+d][m]^-1;
		 bool p2=f2[400-d][m]^-1;
	  	 if (!p1&&!p2) continue;
	  	 if (p1&&p2) return f2[400+d][m]>f2[400-d][m]?400+d:400-d;
	     else return p1?400+d:400-d;
	  }
}
stack<int> st;
signed main()
{
	int count=0;
	while (scanf("%d%d",&n,&m)==2&&n)
	  {
	  	 for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
	  	 memset(p,0,sizeof(p));
	  	 memset(f1,-1,sizeof(f1));
	  	 f1[400][0]=0;
	  	 dp();
	  	 int j=get(),k=m;
	  	 int sum1=0,sum2=0;
	  	 while (!st.empty()) st.pop();
	  	 for (int i=n;i>=1;i--)
	  	   if ((1<<k)&p[i][j])
	  	     {
	  	        sum1+=a[i]; sum2+=b[i];
	  	        st.push(i);
	  	        j-=a[i]-b[i];
				k--;	
			 }
		 printf("Jury #%d\n",++count);
		 printf("Best jury has value %d for prosecution and value %d for defence:\n",sum1,sum2);
		 while (!st.empty()) 
		   {
		   	  printf(" %d",st.top());
		   	  st.pop();
		   }
		 printf("\n\n");
	  }
	return 0;
}