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