罗大神说这题很简单，，，，然而我着实写的很难过。。。

---

题目链接：

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=110495#problem/K

题意：

给定n个人对罪犯的d值和p值，从中选m个人使得abs(sum(d)−sum(p))最小，如果有多种情况则输出sum(p)+sum(d)最大的情况，并升序输出选择的人的编号。

分析：

这题是既要考虑差又要考虑和。还是绝对值最小。。刚看见有点懵逼。

其实不方，这题d和p最大只有20，m最大又只有20，就是说差的绝对值最大只有20 * 20，

那么我们设dp[i][j]为已经选出i个人，sum(p)−sum(d)为j的最大sum(p)+sum(d)。dp[i][j]=−1 表示这个状态无法达到。

那么问题来了，绝对值怎么处理，如果sum(p)−sum(d)小于0怎么办。。。

我们知道差的绝对值最大为20 * 20，那么我们给每个差都加上20 * 20 ，保证j大于等于0，这样就相当于以20 * 20 为原点，最终只要找到距离20 * 20 最近的dp值大于等于0的点就好了。。

想到这里就差不多了。。

很容易得到状态转移方程。

对于每个i和j的状态枚举给定的n个人，注意判断之前当前这个人之前是否出现过。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define sa(a) scanf("%d", &a)

#define sal(a) scanf("%I64d", &a)

const int maxn = 1000 + 5, maxm = 200 + 5, INF = 0x3f3f3f3f;

int p[maxm], d[maxm];

struct DP{int a; int now;};

DP dp[20 + 5][maxn];

int tt[maxn];

int cnt;

void output(int he, int ans)

{

    if(he == 0) return;

    int index = dp[he][ans].now;

    tt[he--] = index;

    output(he, ans - p[index] + d[index]);

}

bool vis(int i, int j, int k)

{

    while(i >= 0){

        int index = dp[i][j].now;

        if(index == k) return true;

        i--;

        j -= p[index] - d[index];

    }

    return false;

}

int main (void)

{

   int n, m;

   int cnt = 1;

   while(scanf("%d%d", &n, &m) && n + m){

      for(int i = 0; i < n; i++){

            sa(p[i]); sa(d[i]);

      }

      int t = m * 20;

      for(int i = 0; i <= m; i++){

        for(int j = 0; j <= 2 * t; j++){

            dp[i][j].a = -1;

            dp[i][j].now = -1;

        }

      }

      dp[0][t].a = 0;

      for(int i = 0; i < m; i++){

        for(int j = 0; j <= t * 2; j++){

            if(dp[i][j].a < 0) continue;//状态无法到达

            for(int k = 0; k < n; k++){

                if(dp[i][j].a + p[k] + d[k] > dp[i + 1][j + p[k] - d[k]].a){

                    if(vis(i, j, k)) continue;//之前出现过

                    dp[i + 1][j + p[k] - d[k]].a = dp[i][j].a + p[k] + d[k];

                    dp[i + 1][j + p[k] - d[k]].now = k;

                }

            }

        }

      }

        int i = 0;

        while(dp[m][t + i].a < 0 && dp[m][t - i].a < 0) i++;

        int ans;

        if(dp[m][t + i].a > dp[m][t - i].a) ans = t + i;

        else ans = t - i;

        printf("Jury #%d\n", cnt++);

        printf("Best jury has value %d for prosecution and value %d for defence:\n",

               (ans - t + dp[m][ans].a)/2, (dp[m][ans].a - ans + t)/2);

        output(m, ans);

        sort(tt + 1, tt + m + 1);

        for(int i = 1; i <= m; i++)

            printf(" %d%c", tt[i] + 1, i == m?'\n':' ');

        printf("\n");

   }

   return 0;

}