POJ1015 Jury Compromise

发表于 | 分类于 |
字数统计: 492 字

题目链接

题解

该题不难，但是很坑，如果单纯按照二维背包做容易出现最优解重复的问题。
所以要完整的记录路径。
其他的就是基本的背包了，把一维体积设定为两和之差即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, a[205], b[205];
int f[25][1005] = {0}, pos[25][1005], aans[25];
int sel[25][1005][25] = {0};
void init(){
    for(int i = 1; i <= n; ++i)
        a[i] = read(), b[i] = read();
    memset(f, 0xc0, sizeof(f));
    memset(pos, 0, sizeof(pos));
    memset(sel, 0, sizeof(sel));
}
void solve(){
    f[0][500] = 0;
    for(int i = n; i >= 1; --i){
        for(int j = m; j >= 1; --j){
            int dif = a[i] - b[i];
            int lim = min(0, dif) + 500;
            for(int k = -500 + max(0, dif); k <= lim; ++k){
                if(f[j - 1][k + 500 - dif] < 0) continue;
                if(f[j - 1][k + 500 - dif] + a[i] + b[i] > f[j][k + 500]){
                    f[j][k + 500] = f[j - 1][k - dif + 500] + a[i] + b[i], 
                    pos[j][k + 500] = k - dif + 500;
                    for (int o = j - 1; o >= 1; --o)
                        sel[j][k + 500][o] = sel[j - 1][k - dif + 500][o];
                    sel[j][k + 500][j] = i;
                }
            }
        }
    }
    int ans, jj, kk, dif;
    for(int i = 0; i <= 500; ++i)
        if(f[m][500 - i] >= 0 || f[m][500 + i] >= 0){
            if(f[m][500 - i] < f[m][500 + i])
                ans = f[m][500 + i], dif = i, jj = m, kk = 500 + i;
            else
                ans = f[m][500 - i], dif = -i, jj = m, kk = 500 - i;
            break;
        }
    printf("Best jury has value %d for prosecution and value %d for defence:\n", (ans + dif) >> 1, (ans - dif) >> 1);
    for(int i = 1; i <= m; ++i)
        aans[i] = sel[jj][kk][i];
    sort(aans + 1, aans + m + 1);
    for(int i = 1; i <= m; ++i)
        printf(" %d", aans[i]);
    printf("\n\n");
}
int main(){
    int T = 1;
    while((n = read()) && (m = read())){
        printf("Jury #%d\n", T);
        init();
        solve();
        T++;
    }
    return 0;
}

Powered By Valine
v1.5.2