POJ – 1015 Jury Compromise

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;
}