社区讨论
求助,输出方案
UVA323Jury Compromise参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lobwlhgf
- 此快照首次捕获于
- 2023/10/30 04:08 2 年前
- 此快照最后确认于
- 2023/11/04 09:12 2 年前
CPP
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 255, M = 35;
struct rec
{
int w1, w2;
} man[N];
int n, m;
int f[N][M][450];
vector<int> ans;
int main()
{
int Case = 0;
while(scanf("%d%d", &n, &m) == 2, n || m)
{
ans.clear();
memset(man, 0, sizeof man);
for(int i = 1; i <= n; i ++)
scanf("%d%d", &man[i].w1, &man[i].w2);
memset(f, 0x3f, sizeof f);
f[0][0][0] = 0;
for(int i = 1; i <= n; i ++)
for(int j = 0; j <= m; j ++)
for(int k = 0; k <= 400; k ++)
{
f[i][j][k] = f[i-1][j][k];
if(j > 0 && k >= man[i].w1+man[i].w2 && abs(f[i][j][k]) >= abs(f[i-1][j-1][k-man[i].w1-man[i].w2] + man[i].w1 - man[i].w2))
{
f[i][j][k] = f[i-1][j-1][k-man[i].w1-man[i].w2]+man[i].w1-man[i].w2;
}
// if(f[i][j][k] <= 0x3f3f3f3f/2) printf("f[%d][%d][%d] = %d\n", i, j, k, f[i][j][k]);
}
int dx = 0x3f3f3f3f, sum = 0;
for(int i = n; i >= 0; i --)
for(int j = 400; j >= 0; j --)
if(abs(dx) > abs(f[i][m][j]) || (abs(dx) == abs(f[i][m][j]) && j > sum))
{
dx = f[i][m][j];
sum = j;
}
int p = dx+sum>>1, d = sum-p;
printf("Jury #%d\nBest jury has value %d for prosecution and value %d for defence:\n", ++ Case, p, d);
for(int i = m; i <= n; i ++)
if(f[i][m][sum] == dx)
{
n = i;
break;
}
for(int i = n, j = m; i >= 1 && j; i --)
{
if(f[i][j][sum] == dx && sum >= man[i].w1-man[i].w2 && f[i-1][j-1][sum-man[i].w1-man[i].w2]+man[i].w1-man[i].w2 == dx)
{
ans.push_back(i);
dx = dx-man[i].w1+man[i].w2;
sum = sum-man[i].w1-man[i].w2;
j --;
}
}
for(int i = ans.size()-1; i >= 0; i --)
printf(" %d", ans[i]);
cout << endl << endl;
}
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...