描述
题解
我真想吐槽这次比赛出题人是多么的糙,题意难以理解也就算了,还有错别字……有强迫症的我十分痛苦。
反正又是一个 dp ,有些像 01 背包,看看代码吧,没啥太大区别。虽然也有那么一丢丢的差别,主要是要记录一下哪些选取了而已。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#define clr(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int MAXN = 111;
const int MAXB = 1111;
struct meal
{
int score, cost;
} m[MAXN];
int B, N;
int dp[MAXB];
bool tmp[MAXN];
bool vis[MAXN][MAXB];
int main()
{
int T, ce = 1;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &B, &N);
for (int i = 1; i <= N; i++)
{
scanf("%d%d", &m[i].score, &m[i].cost);
}
clr(dp, 0);
clr(tmp, 0);
clr(vis, false);
for (int i = 1; i <= N; i++)
{
for (int j = B; j >= 0; j--)
{
if (j >= m[i].cost)
{
if (dp[j] < dp[j - m[i].cost] + m[i].score)
{
vis[i][j] = true;
dp[j] = dp[j - m[i].cost] + m[i].score;
}
else
{
vis[i][j] = false;
}
}
}
}
int t = B, cnt = 0;
for (int i = N; i >= 1; i--)
{
if (vis[i][t])
{
tmp[i] = true;
t -= m[i].cost;
cnt++;
}
}
printf("Case #%d:\n%d %d\n", ce++, dp[B], B - t);
for (int i = 1; i <= N; i++)
{
if (tmp[i])
{
printf("%d%c", i, (--cnt == 0) ? '\n' : ' ');
}
}
}
return 0;
}