https://biancheng.love/contest-ng/index.html#/131/problems
首先，去到n点的最小时间是所有数加起来。
然后，如果我1 --- 2，然后再2--1，那么，就相当于从1继续开始，只不过是时间变化了。
所以，以后的每一步的代价都是2 * a[i]
那么设dp[v]表示时间是v时，能否到达点n。我可以走a[1] 4次，也就是1--2 2---1 再 1---2 、2---1，都是改变了开始值。
那么进行一个完全背包的dp即可
dp[sum] = true
然后转移。
/*
Author: liuweiming1997
Result: AC Submission_id: 226644
Created at: Sun Dec 18 2016 14:53:09 GMT+0800 (CST)
Problem_id: 587 Time: 17 Memory: 2788
*/ #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
int n, m;
const int maxn = + ;
int a[maxn];
vector<int>gg;
bool dp[ + ];
void work() {
scanf("%d%d", &n, &m);
int all = ;
for (int i = ; i <= n - ; ++i) {
scanf("%d", &a[i]);
all += a[i];
a[i] *= ;
}
memset(dp, , sizeof dp);
dp[all] = true;
for (int i = ; i <= n - ; ++i) {
for (int j = a[i]; j <= m; ++j) {
dp[j] = dp[j] || dp[j - a[i]];
}
}
gg.clear();
for (int i = ; i <= m; ++i) {
if (!dp[i]) {
gg.push_back(i);
}
}
for (int i = ; i < gg.size() - ; ++i) {
printf("%d ", gg[i]);
}
printf("%d\n", gg.back());
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
其实这题的原题是，
求解
3 * x + 4 * y + 5 * z <= m的解的个数，之类的题目。
x >= 0
y >= 0
z >= 0
解法就是，设dp[v]表示3 * x + 4 * y + 5 * z能否生成v。一开始的时候，dp[0] = true;这个可以带入验证
然后，
for (int i = 1; i <= n; ++i) //枚举每一种数字，就是a[1] = 3, a[2] = 4. a[3] = 5
for (int v = a[i]; v <= m; ++v) //枚举每一个背包。
dp[v] = dp[v] || dp[v - a[i]] //完全背包思想