题意：从n个人中选出m个，每个人有固定的p值，d值，要求使m个人的p总和和d总和的差的绝对值最小，若有多解则取两者和最大的。

分析：dp

本题为special judge，不需要考虑多解情况。

f[i][j]表示在选m个人中的第i个人的时候使所有已选中的人的p,d差为j时，所能获得的p,d最大和。

f[i + 1][j + p[k] - d[k]] = f[i][j] + p[k] + d[k];(要求k之前没有选过，要查看f[i][j]的完整路径，确保无k)

填写完成后，观察f[m]找到最小差值，最大和。知道和差自然可以求出总的p,d。

也可以用另一种方法：

三维f[i,j,k]表示前i取j差值为k的最大和

f[i,j,k]=max{f[i-1,j,k],f[i-1,j-1,k-s1[i]]+s2[i]}

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            usingnamespace std; #define maxn 205 #define maxm 25 int n, m, w; int f[maxm][maxn *10]; int p[maxn], d[maxn]; int path[maxm][maxn *10]; bool vis[maxn]; int stk[maxn]; void input() {
     for (int i =0; i < n; i++)         scanf("%d%d", &p[i], &d[i]); } void getpath(int i, int j) {
         memset(vis, 0, sizeof(vis)); while (path[i][j] !=-1)     {
     int k = path[i][j];         vis[k] =true;         i--;         j -= p[k] - d[k];     } } void make(int i, int j, int k) {
     int a = p[k] + d[k]; int b = p[k] - d[k]; if (f[i +1][j + b] ==-1|| f[i +1][j + b] < f[i][j] + a)     {
             f[i +1][j + b] = f[i][j] + a;         path[i +1][j + b] = k; return;     } } void work() {
         w = m *20;     memset(f, -1, sizeof(f));     memset(path, -1, sizeof(path));     f[0][w] =0; for (int i =0; i < m; i++) for (int j =0; j <=2* w; j++) if (f[i][j] !=-1)             {
                     getpath(i, j); for (int k =0; k < n; k++) if (!vis[k])                         make(i, j, k);             } int d1 =-1, d2 =-1, dd; for (int i =0; i <= w; i++) if (f[m][w + i] !=-1)         {
                 d1 = i; break;         } for (int i =0; i <= w; i++) if (f[m][w - i] !=-1)         {
                 d2 = i; break;         } if (d1 ==-1|| (d2 < d1 && d2 !=-1))         dd = w - d2; elseif (d2 ==-1|| (d1 < d2 && d1 !=-1))         dd = w + d1; elseif (f[m][w + d1] > f[m][w - d2])         dd = w + d1; else         dd = w - d2; int a = f[m][dd]; int b = dd - w; int ansp = (a + b) /2; int ansd = (a - b) /2;     printf("Best jury has value %d for prosecution and value %d for defence:\n", ansp, ansd); int top =0;     a = m;     b = dd; while (path[a][b] !=-1)         {
     int k = path[a][b];             stk[top++] = k;             a--;             b -= p[k] - d[k];         }     sort(stk, stk + top); for (int i =0; i < top; i++)         printf(" %d", stk[i] +1);     putchar('\n');     putchar('\n'); } int main() {
     //freopen("t.txt", "r", stdin); int t =0; while (scanf("%d%d", &n, &m), n | m)     {
             t++;         printf("Jury #%d\n", t);         input();         work();     } return0; }