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

懵逼的 题目

传送至 Vijos

扯淡的 题解

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

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

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

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的前驱都是第一次到达这个容积的牌的编号
大概是这样

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…

#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