POJ 1015
f[i][j][k]:从前i个人中选j个人,辩控差为k时的最大辩控和
状态转移即在第i(i<=j)个阶段,要么选第i个人,要么不选第i个人.
其实是个01背包.
注意下标范围,防负数出现.
嗯…代码写得挫,先这样吧.
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
#include<cstring>
using namespace std;
int p[201], d[201];
int f[201][21][801];
int P, D, N, M;
int ans[21];
struct Path {
int n, m, k, id;
} path[201][21][801];
void goBack(int n, int m, int k) { //状态回溯
int cnt = 0;
while (path[n][m][k].id) {
int next_n = path[n][m][k].n;
int next_m = path[n][m][k].m;
int next_k = path[n][m][k].k;
if (path[n][m][k].id != path[next_n][next_m][next_k].id)
ans[cnt++] = path[n][m][k].id;
n = next_n, m = next_m, k = next_k;
}
}
int main() {
int kase = 0;
while (cin >> N >> M && N&&M) {
for (int i = 1; i <= N; ++i) {
cin >> p[i] >> d[i];
}
P = 0, D = 0;
memset(f,-1,sizeof(f));
path[0][0][400].id=0;
f[0][0][400] = 0;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= M; ++j) {
for (int k = -400; k <= 400; ++k) {
if (j > 0 && k + p[i]-d[i] + 400 >= 0 && k + p[i]-d[i] + 400 <= 800 &&
f[i - 1][j - 1][k + 400] != -1 &&
f[i][j][k + p[i]-d[i] + 400] < f[i - 1][j - 1][k + 400] + p[i]+d[i]) {
f[i][j][k + 400 + p[i]-d[i]] = f[i - 1][j - 1][k + 400] + p[i]+d[i];
path[i][j][k + 400 + p[i]-d[i]].id = i;
path[i][j][k + 400 + p[i]-d[i]].k = k + 400;
path[i][j][k + 400 + p[i]-d[i]].m = j - 1;
path[i][j][k + 400 + p[i]-d[i]].n = i - 1;
}
if (f[i - 1][j][k + 400] != -1 &&
f[i - 1][j][k + 400] > f[i][j][k + 400]) {
f[i][j][k + 400] = f[i - 1][j][k + 400];
path[i][j][k + 400].id = path[i - 1][j][k + 400].id;
path[i][j][k + 400].k = k + 400;
path[i][j][k + 400].m = j;
path[i][j][k + 400].n = i - 1;
}
}
}
}
for (int k = 0; k <= 400; ++k) {
if (f[N][M][400 + k] != -1 || f[N][M][400 - k] != -1) {
if (f[N][M][400 + k] > f[N][M][400 - k]) {
goBack(N, M, k + 400);
P = (f[N][M][400 + k] + k) / 2;
D = (f[N][M][400 + k] - k) / 2;
} else {
goBack(N, M, 400 - k);
P = (f[N][M][400 - k] - k) / 2;
D = (f[N][M][400 - k] + k) / 2;
}
printf("Jury #%d\n", ++kase);
printf(
"Best jury has value %d for prosecution and value %d for "
"defence:\n",
P, D);
for (int i = M - 1; i >= 0; --i) {
printf(" %d", ans[i]);
}
printf("\n");
break;
}
}
}
return 0;
}