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 = 100 + 20; int a[maxn]; vector<int>gg; bool dp[500 + 20]; void work() { scanf("%d%d", &n, &m); int all = 0; for (int i = 1; i <= n - 1; ++i) { scanf("%d", &a[i]); all += a[i]; a[i] *= 2; } memset(dp, 0, sizeof dp); dp[all] = true; for (int i = 1; i <= n - 1; ++i) { for (int j = a[i]; j <= m; ++j) { dp[j] = dp[j] || dp[j - a[i]]; } } gg.clear(); for (int i = 1; i <= m; ++i) { if (!dp[i]) { gg.push_back(i); } } for (int i = 0; i < gg.size() - 1; ++i) { printf("%d ", gg[i]); } printf("%d ", 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 0; }
其实这题的原题是，
求解
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]] //完全背包思想