poj 1015Jury Compromise解题报告

这样类型的题，我觉得应该归类为递推的dp，dp[j][k]表示选j个人达到k=|D(j)-P(j)|时的最大的D(j)+P(j)并且用path[j][k]记录最后一步的选择的编号，输出的时候要对路径上的点进行一遍升序的排序。而且为了能够处理绝对值的问题，加一个修正值fix=m*20则得到的结果都在这个fix的两边，此时fix相当于坐标原点，并且这里要用到一个和修正值有关的公式设div为D(j)-p(j)+fix,我们可以从dp[j][k]里得到D(j)+P(j)，则D(j)和P(j)可以用fix，div，以及dp[j][k]表示出来。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define N 205
#define M 25
#define K 805
using namespace std;
int dp[M][K];
int path[M][K];
int d[N],p[N];
int v[N],sum[N];
int sel[M];
bool havese(int j,int k,int i)
{
    while(j>0&&path[j][k]!=i)
    {
        k-=v[path[j][k]];
        j--;
    }
    return j?true:false;
}
int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
int main()
{
    int n,m,i,j,k,fix;
    int icase=1;
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        memset(dp,-1,sizeof(dp));
        memset(path,0,sizeof(path));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&d[i],&p[i]);
            v[i]=d[i]-p[i];
            sum[i]=d[i]+p[i];
        }
        fix=m*20;
        dp[0][fix]=0;
        for(j=1;j<=m;j++)
        for(k=0;k<=2*fix;k++)
        {
            if(dp[j-1][k]!=-1)
            {
                for(i=1;i<=n;i++)
                {
                    if(!havese(j-1,k,i)&&dp[j][k+v[i]]<dp[j-1][k]+sum[i])
                    {
                        dp[j][k+v[i]]=dp[j-1][k]+sum[i];
                        path[j][k+v[i]]=i;
                    }
                }
            }
        }
        for(i=0;i<=fix;i++)
        if(dp[m][fix-i]!=-1||dp[m][fix+i]!=-1)
        break;
        int div=dp[m][fix-i]>dp[m][fix+i]?(fix-i):(fix+i);
        int dv=(dp[m][div]+div-fix)>>1;
        int pv=(dp[m][div]-div+fix)>>1;
        printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n",icase++,dv,pv);
        k=0;
        i=div;
        for(j=m;j>0;j--)
        {
            sel[k++]=path[j][i];
            i-=v[path[j][i]];
        }
        qsort(sel,k,sizeof(int),cmp);
        for(i=0;i<m;i++)
        {
            printf(" %d",sel[i]);
        }
        printf("\n");
    }
    return 0;
}