## poj1015 Jury Compromise - dp，背包模型 原

m2012

``````#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdlib>
using namespace std;

int like[202];
int dislike[202];
int N, M;
int f[200 + 1][20 + 1][1600 + 2];
char pre[200 + 1][20 + 1][1600 + 2];
vector<int> ansList;
int testN;

const int nil = -2000000;
int dp(int n, int m, int d) {
// printf("==== %d %d %d\n", n, m, d);
return f[n][m][d + 800];
}

void input() {
int i, j, k;
scanf("%d %d", &N, &M);
if (N == 0) exit(0);
for (i = 1; i <= N; ++i) {
scanf("%d %d", &(like[i]), &(dislike[i]));
}

for (i = 0; i < 201; ++i)
for (j  = 0; j < 20 + 1; ++j)
for (k = 0; k < 1600 + 2; ++k) {
f[i][j][k] = nil;
pre[i][j][k] = 'w';
}
}

void traceBack(int n, int m, int d) {
while (1) {
char & son = pre[n][m][d + 800];
// printf("*** %d %d %d %c\n", n, m, d, son);

assert(n >= 1);

if (son == '+') {
ansList.push_back(n);
d = d - (like[n] - dislike[n]);
n = n - 1;
m = m - 1;
continue;
}

if (son == '-'){
n = n - 1;
continue;
}

if (son == 'e') break;
if (son == 'E') {
ansList.push_back(1);
break;
}

assert(0);

}
}

void run() {
input();

int n, m, d;
for (n = 1; n <= N; ++n) {
for (m = 0; m <= n && m <= M; ++m) {
for (d = -800; d <= 800; ++d) {
int & ans = f[n][m][d + 800];
char & son = pre[n][m][d + 800];

if (n == 1) {
if (m == 0) {
if (d == 0) { son = 'e'; ans = 0; continue; }
else { son = 'x'; ans = -1; continue; }
} else if (m == 1) {
if (d == like[1] - dislike[1]) { son = 'E'; ans = like[1] + dislike[1]; continue; }
else { son = 'y'; ans = -1; continue; }
}

assert(0);
}

ans = -1;
son = 'p';
int c = like[n] - dislike[n];
if (n - 1 >= m && dp(n - 1, m, d) != -1) {
ans = dp(n - 1, m, d);
son = '-';
}

if (n >= m && m >= 1 && dp(n - 1, m - 1, d - c) != -1 && (ans == -1 || ans < dp(n - 1, m - 1, d - c) + like[n] + dislike[n]) ) {
ans = dp(n - 1, m - 1, d - c) + like[n] + dislike[n];
son = '+';
}
}
}
}

int i, ans;
for (i = 0; i <= 800; ++i) {
if (dp(N, M, i) != -1 && dp(N, M, -i) == -1) {
ans = i;
break;
}
if (dp(N, M, i) == -1 && dp(N, M, -i) != -1) {
ans = -i;
break;
}
if (dp(N, M, i) != -1 && dp(N, M, -i) != -1 && dp(N, M, i) >= dp(N, M, -i)) {
ans = i;
break;
}
if (dp(N, M, i) != -1 && dp(N, M, -i) != -1 && dp(N, M, i) < dp(N, M, -i)) {
ans = -i;
break;
}
}

ansList.clear();
traceBack(N, M, ans);

printf("Jury #%d\n", testN);
printf("Best jury has value %d for prosecution and value %d for defence:\n",  (ans + dp(N, M, ans))/2,  -(ans - dp(N, M, ans))/2);

sort(ansList.begin(), ansList.end());
for (i = 0; i < ansList.size(); ++i) {
printf(" %d", ansList[i]);
}
printf("\n\n");
}

int main() {
for (testN = 1; true; ++testN)
run();
return 0;
}``````

### m2012

Playboy002
2015/07/17
42
0

2018/03/08
0
0

2018/12/14
0
0
HDU 2602 Bone Collector（01背包）

Bone Collector 　　Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s ,......

suvvm
2018/11/08
0
0
HDU 2191 悼念512汶川大地震遇难同胞

suvvm
2018/11/07
0
0

Vert.x系列（二）--EventBusImpl源码分析

37分钟前
1
0
Perl - 获取文件项目

wffger

2
0
vue组件系列3、查询下载

2
0
java浅复制和深复制

woshixin

1
0
kubernetes 二进制包安装

Colben

10
0