POJ1015解题报告

原题：思路：|D-P|尽可能的小，而D+P尽可能的大。
显然|D-P|是没有最优子结构的，但是 0<=D,P<=20，而 1<=M<=20，所以可以
枚举|D-P|的值，-400<=D-P<=400，所以可以用数组 
state[M+1][801]记录所以的情况。每来一个候选人，更新所有的记录和路径，
D+P根据题目要求是有最优结构的。类似于背包问题。

关键这道题目要求打印组合形式，我就暴力开数组记录每个状态的路径来完成，肯定
有好方法。
还有，要当心 D,P == 0的情况。

代码：

#include <iostream>
#include <cstring>

using namespace std;

#define N 201
#define M 21
#define MAX 801
#define BIAS 400

struct Node {
    bool valid;
    int sum;
    int id[M];
};

Node state[M][MAX];
int m, n;
int array[N][2];

void init() {
    for (int i=1; i<=n; i++)
        cin >> array[i][0] >> array[i][1];
    memset(state, 0, sizeof(state));
    state[0][BIAS].valid = true;
}

int dp() {
    for (int i=1; i<=n; i++) {
        int diff = array[i][0] - array[i][1];
        int sum = array[i][0] + array[i][1];
        for (int j=m; j>0; j--) {
            for (int x=0; x<MAX; x++) {
                if (state[j-1][x].valid) {
                    if (state[j-1][x].sum + sum >= state[j][x+diff].sum) {
                        state[j][x+diff].sum = state[j-1][x].sum + sum;
                        for (int index=1; index<j; index++)
                            state[j][x+diff].id[index] = state[j-1][x].id[index];
                        state[j][x+diff].id[j] = i;
                        state[j][x+diff].valid = true;
                    }
                }
            }
        }
    }
    for (int i=0; i<=BIAS; i++)
        if (state[m][BIAS+i].valid || state[m][BIAS-i].valid) {
            int maxSum = -1;
            if (state[m][BIAS+i].valid)
                maxSum = state[m][BIAS+i].sum;
            if (state[m][BIAS-i].valid && state[m][BIAS-i].sum > maxSum)
                return BIAS-i;
            return BIAS+i;
        }
}

int main() {
    int id = 0;
    while (cin >> n >> m) {
        if (n == 0 && m == 0)
            return 0;
        id++;
        init();
        int diff = dp();
        cout << "Jury #" << id << endl;
        cout << "Best jury has value "
            << ((state[m][diff].sum+diff-BIAS)/2)
            << " for prosecution and value "
            << ((state[m][diff].sum-diff+BIAS)/2)
            << " for defence:\n";
        for (int i=1; i<=m; i++)
            cout << " " << state[m][diff].id[i];
        cout << endl;
        cout << endl;
    }
    return 0;
}