zoj1303.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <algorithm>
#define MAX 21
#define LEN 201
using namespace std;

int dif[LEN], sum[LEN];
int path[MAX][2 * MAX * MAX + 1];
int f[2][2 * MAX * MAX + 1];
int n, m;

void solve() {
    int i, j, k, l1,l2;
    int ans[MAX], p;
    int max;
   
    for (i = 0; i < m; i++) memset(path[i], 0xff, sizeof(path[i]));
    memset(f[0], 0xff, sizeof(f[0]));
    p = 0; max = MAX * m;
    for (i = 0; i < n; i++) 
        if (sum[i] > f[0][max + dif[i]]) {
            path[0][max + dif[i]] = i;
            f[0][max + dif[i]] = sum[i];
        }
    for (j = 1; j < m ; j++){
        memset(f[1-p], 0xff, sizeof(f[1-p]));
        for (k = 0; k < 2 * max; k++) if (path[j-1][k] >= 0)
            for (i = 0; i < n; i++) if (f[1-p][k + dif[i]] < f[p][k] + sum[i]) {
                for (l1 = j - 1, l2 = k; l1 >= 0; l1 --) {
                    if (path[l1][l2] == i) break;
                    l2 -= dif[path[l1][l2]];
                }
                if (l1 < 0) {
                    path[j][k + dif[i]] = i;
                    f[1-p][k + dif[i]] = f[p][k] + sum[i];
                }
            }
        p = 1 - p;
    }
    
    p = (m - 1) % 2;
    for (i = 0; i <= max; i++) {
        if (f[p][max + i] >= 0 || f[p][max - i] >= 0) {
            if (f[p][max + i] > f[p][max - i]) i = max + i;else i = max - i;
            break;
        }
    }
    printf("Best jury has value %d for prosecution and value %d for defence:\n", (f[p][i]+(i-max))/2, (f[p][i]-(i-max))/2);
    for(j = m - 1; j >= 0; j--) {
        ans[j] = path[j][i] + 1;
        i -= dif[path[j][i]];
    }
    sort(ans, ans + m);
    for (i = 0; i < m; i++) printf(" %d", ans[i]);
    printf("\n\n");
}

int main() {
    int tc = 0;
    while(scanf("%d%d", &n, &m), n + m) {
        printf("Jury #%d\n",++tc);
        int a ,b;
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &a, &b);
            dif[i] = a - b;
            sum[i] = b + a;
        }
        solve();   
    }
    return 0;
}