题目大意： 在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n 个人作为陪审团的候选人，然后再从这n 个人中选m 人组成陪审团。选m 人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0 到20。为了公平起见，法官选出陪审团的原则是：选出的m 个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。(d[k]为控方对每个人的评分，p[k]为辩方对每个人的评分)


解题思路：1）第一感觉就是个背包，n个人每一个都有取和不取的两种情况。
              2）设状态：对于每一个可行的方案，有三个量，一个是陪审团的人数，一个是差值，一个是和。很明显，在题目中，我们可以知道陪审团的人数是有范围的，而且差值是有范围（-400，400）
                   我们不妨设dp[i][j]表示由i个人组成的陪审团，差值为j的方案的总分最大和。
              3）状态的转移：其实可以发现，对于每一个方案dp[i][j]，都可以由方案dp[i-1][j+d[k]-p[k]]+d[k]+p[k](1<=k<=n)变换而来。
              4）这里j表示的是差值，由于差值的范围是-400到400，由于C++中坐标不能为负数，所以要加上400变为0到800即可以处理这个问题。


代码：
  1#include <iostream>
  2#include <cstdio>
  3#include <cstring>
  4#include <cmath>
  5#include <string>
  6#include <algorithm>
  7
  8using namespace std;
  9
 10struct player
 11{
 12    int d,p;
 13}num[300];              //表示控方和辩方分别给的分数
 14int result[300];        //储存最终的m个陪审团成员
 15int n,m,x,y,xx,yy;
 16int path[30][1000];     //记录选择i个人，以差值j结尾的陪审团成员的最后一个人
 17int dp[30][1000];       //记录选择i个人，差值为j的最大和是多少
 18
 19void init()
 20{
 21    memset(path,0,sizeof(path));
 22    memset(result,0,sizeof(result));
 23    for (int i=0; i<=m; i++)
 24      for (int j=0; j<=800; j++)
 25      {
 26          dp[i][j]=-1;
 27      }
 28    dp[0][400]=0;                   //400是贯穿整个程序的，目的是为了使差值由负变正，可以在数组在中储存
 29}
 30
 31void get_dp()
 32{
 33    for (int i=0; i<=m-1; i++)
 34    {
 35        for (int j=0; j<=800; j++)
 36        {
 37            for (int l=1; l<=n && dp[i][j]>=0; l++)
 38            {
 39                if (dp[i+1][j+num[l].d-num[l].p]<dp[i][j]+num[l].d+num[l].p)
 40                {
 41                    x=i;
 42                    y=j;
 43                    while(x>0&&path[x][y]!=l)
 44                    {
 45                        y-=num[path[x][y]].d-num[path[x][y]].p;       //判断这个新加入的l在原来的成立的陪审团中是否存在
 46                        x--;
 47                    }
 48                    if(x==0)
 49                    {
 50                        dp[i+1][j+num[l].d-num[l].p]=dp[i][j]+num[l].d+num[l].p;
 51                        path[i+1][j+num[l].d-num[l].p]=l;
 52                    }
 53                }
 54            }
 55        }
 56    }
 57}
 58
 59int cmp(int a,int b)
 60{
 61    return a<b;
 62}
 63
 64int main()
 65{
 66    int T=0;
 67    while (~scanf("%d%d",&n,&m))
 68    {
 69        T++;
 70        if (n==0 && m==0) break;
 71        init();                     //初始化
 72        int xx,yy;
 73        for (int i=1; i<=n; i++)
 74        {
 75            scanf("%d%d",&xx,&yy);
 76            num[i].d=xx;
 77            num[i].p=yy;
 78        }
 79        get_dp();                             //dp[i][j]表示的是选择i个人，差值为j的最大和是多少
 80        int k=0;
 81        int i=400;                            //400是贯穿整个程序的，目的是为了使差值由负变正，可以在数组在中储存
 82        int temp;
 83        while (dp[m][i+k]<0 && dp[m][i-k]<0) k++;            //求出最小的差值
 84
 85
 86        //找出m个人的陪审团成员，和统计m个人的陪审团控方得分和和辩方得分和
 87        if (dp[m][i+k]>dp[m][i-k]) temp=i+k;
 88            else temp=i-k;
 89        int x=y=0;
 90         for(int i=0; i<=m-1; i++)
 91        {
 92            result[i]=path[m-i][temp];
 93            x+=num[result[i]].d;
 94            y+=num[result[i]].p;
 95            temp-=num[result[i]].d-num[result[i]].p;
 96        }
 97
 98        //题目要求从小到大输出~第一次就WA在这里，注意审题
 99        sort(result,result+m,cmp);
100
101        cout << "Jury #" << T << endl;
102        cout << "Best jury has value " << x << " for prosecution and value " << y << " for defence:" << endl;
103        for (int i=0; i<=m-1; i++)
104            cout << " " << result[i];
105        cout << endl;
106    }
107    return 0;
108}
109