AcWing 280. 陪审团
原题链接
中等
作者:
Zar13
,
2022-08-16 23:47:14
,
所有人可见
,
阅读 187
acwing 280 陪审团
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int dp[N][21][820];
const int base = 400;
int pr[N];
int de[N];
int divs[N];//节省一点点计算时间
int n, m;
int main()
{
int cases = 1;
while (1)
{
scanf("%d%d", &n, &m);
if (!n)
{
break;
}
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &pr[i], &de[i]);
divs[i] = pr[i] - de[i];
}
memset(dp, -0x3f, sizeof dp);//初始化为负无穷
dp[0][0][base] = 0;//初始条件
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)//j要从0开始,考虑一个都补选的情况
{
for (int k = 0; k <= 800; ++k)
{
dp[i][j][k] = dp[i - 1][j][k];
int t = k - divs[i];
if (j > 0)
{
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][t] + pr[i] + de[i]);
}
}
}
}
int k, i = 0;
//寻找最优解
while (dp[n][m][base + i] < 0 && dp[n][m][base - i] < 0)
{
i++;
}
if (dp[n][m][base + i] > dp[n][m][base - i])
{
k = base + i;
}
else
{
k = base - i;
}
int ans[22];
int idx = 0;
int prsum = 0, desum = 0;
//回溯选择过程
while (m)
{
if (dp[n][m][k] != dp[n - 1][m][k])
{
prsum += pr[n];
desum += de[n];
ans[idx++] = n;
k -= divs[n];
m--;
}
n--;
}
//输出结果
printf("Jury #%d\n", cases++);
printf("Best jury has value %d for prosecution and value %d for defence:\n", prsum, desum);
sort(ans, ans + idx);
for (int j = 0; j < idx; ++j)
{
printf(" %d", ans[j]);
}
puts("\n");
}
return 0;
}