翻车笔记_ vijos1071 新年趣事之打牌

遇到错误可以手动模拟一下流程

懵逼的 题目

传送至 Vijos

扯淡的 题解

很简单的带输出路径的背包
然后WAWAWA
$%#@^%$^%^

然后没看出来那错了就下课了
今天又来看了看
也没发现什么问题, 就是发现爆了int然后多过了一个点

最后看讨论
发现不能这样记录路径(引用一下原文)

1
2
3
4
5
6
7
8
for(int i = 1; i <= n; ++i)
for(int j = prefix[i]; j >= val[i]; --j)
if(dp[j - val[i]] != inf)
{
if(dp[j] == inf) dp[j] = dp[j - val[i]];
else dp[j] += dp[j - val[i]];
pre[j] = i;
}

因为这样会使多个容积j的前驱为i
所以打印路径的时候会GG
所以应该让每一个容积j的前驱都是第一次到达这个容积的牌的编号
大概是这样

1
2
3
4
5
6
7
for(int i = 1; i <= n; ++i)
for(int j = prefix[i]; j >= val[i]; --j)
if(dp[j - val[i]] != inf)
{
if(dp[j] == inf) dp[j] = dp[j - val[i]], pre[j] = i;// 导致了多个j的pre都是i, 打印的时候会GG
else dp[j] += dp[j - val[i]];
}

然后就A了…

沙茶的 代码

请自动忽略那些丑陋的if…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAXN (100 + 5)
#define MAXW (1000 + 5)
#define LL long long
using namespace std;
int n;
int tot = 0;
int totl;
LL f[MAXN * MAXW];
int fa[MAXN * MAXW];
int w[MAXN];
vector<int> v;
void solve();
void print(int);
void init(int);
bool cmp(int, int);
int main()
{
// std::cout << "Hello, World!" << std::endl;
scanf("%d%d", &totl, &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
tot += w[i];
}
totl = tot - totl;
solve();
return 0;
}
void solve()
{
memset(f, 0, sizeof(f));
f[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = totl; j >= w[i]; j--)
{
if (f[j - w[i]] > 0 || f[j - w[i]] < 0)
{
if (!f[j] && f[j - w[i]] == 1)
fa[j] = i;
f[j] += f[j - w[i]];
}
}
}
if (f[totl] == 0)
puts("0");
else if (f[totl] > 1 || f[totl] < 0)
puts("-1");
else if (f[totl] == 1)
print(totl);
}
void print(int dq)
{
init(dq);
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < v.size(); i++)
{
printf("%d ", v[i]);
}
}
void init(int dq)
{
if (dq > 0)
{
v.push_back(fa[dq]);
init(dq - w[fa[dq]]);
}
}
bool cmp(int x, int y)
{
return x < y;
}

By 联赛期中双爆炸的 Cansult