@Dmaxiya 2020-08-24T16:42:40.000000Z 字数 12719 阅读 1296

DP专题（内含背包）题解

Hello_World

A. Longest Ordered Subsequence

题意

找一个长度为 $n$ 的序列的最长上升子序列。

输入

第一行为一个整数 $n~(1\leq n\leq1000)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(0\leq a_i\leq10000)$ 。

输出

输出最长上升子序列的长度/

样例

输入
7 1 7 3 5 9 4 8
输出
4

题解

最长上升子序列裸题，自学一下把 $O(n\log n)$ 的算法学了。

过题代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 100;
int n, x, cnt, Index;
int dp[maxn];
int main() {
    while(scanf("%d", &n) != EOF) {
        cnt = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &x);
            Index = lower_bound(dp, dp + cnt, x) - dp;
            dp[Index] = x;
            if(Index == cnt) {
                ++cnt;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

B. 数塔

题意

如题。

输入

第一行为一个整数 $C$ ，接下来有 $C$ 组数据，每组数据第一行为一个整数 $N~(1\leq N\leq100)$ ，接下去 $N$ 行第 $i$ 行有 $i$ 个整数，每个整数都在 $[0,99]$ 的范围内。

输出

输出路径最大权值和。

样例

输入
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
输出
30

题解

$dp[i][j]$ 表示从第 $1$ 行第 $1$ 列到第 $i$ 行第 $j$ 列的所有路径中，最大的权值和。
第 $i$ 行第 $j$ 列的值只有两个节点可以到达，即 $(i-1,j-1)$ 和 $(i-1,j)$ 这两个节点，且节点 $(i,j)$ 必然是从这两个节点中路径权值和最大的转移而来，有以下递推式：

$dp[i][j]=\max(dp[i-1][j],dp[i-1,j-1])+num[i][j]$

最后 $\max(dp[n][j])~j\in[1,n]$ 即为答案。

过题代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100 + 100;
int T, n, ans;
int dp[maxn][maxn];
int main() {
    scanf("%d", &T);
    while(T--) {
        ans = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= i; ++j) {
                scanf("%d", &dp[i][j]);
                dp[i][j] += max(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
        for(int i = 1; i <= n; ++i) {
            ans = max(ans, dp[n][i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Bone Collector

题意

$01$ 背包。

输入

第一行为一个整数 $T$ ，接下去有 $T$ 组数据，每组数据第一行为两个整数 $N,V~(N,V\leq1000)$ ，分别表示石头的个数和背包的容量，第二行为 $N$ 个整数，表示每个石头的价值，第三行为 $N$ 个整数，表示每个石头的体积。

输出

输出背包能装下的最大价值。

样例

输入
1 5 10 1 2 3 4 5 5 4 3 2 1
输出
14

题解

$01$ 背包。

过题代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 100;
struct Node {
    int v, w;
};
int T, n, v;
Node node[maxn];
int dp[maxn];
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &v);
        memset(dp, 0, sizeof(int) * (v + 1));
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &node[i].v);
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &node[i].w);
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = v; j >= node[i].w; --j) {
                dp[j] = max(dp[j], dp[j - node[i].w] + node[i].v);
            }
        }
        printf("%d\n", dp[v]);
    }
    return 0;
}

D. Longest Common Substring

题意

求两个字符串的最长公共子串。

输入

多组输入，每组输入为两个长度不超过 $100000$ 的只包含小写字母的字符串，每个字符串一行。

输出

输出最长公共子串的长度。

样例

输入
banana cianaic
输出
3

题解

最长公共子串 $O(n^2)$ 的 $dp$ 解法在题意的链接里已经写得很详细了，可以学习一下，虽然有更快的求最长公共子串的算法，但是这种 $O(n^2)$ 的 $dp$ 思路还是值得一学的，一些关于正则表达式匹配的题目就是用这种 $dp$ 思路再根据题意转化出来的。
由于本题字符串长度达 $10^5$ ，因此 $n^2\approx10^{10}$ 的复杂度 $TLE$ 是必然的，本题要用后缀数组来解，如果没有看完后缀数组的理论部分的话，就不要看这题后面的题解了——
在第一个字符串后面加上一个 $ 符再接第二个字符串后，用后缀数组跑出 $height,sa,rank$ 三个数组，从前往后扫 $height$ 数组，除了 $ 符所在的位置，其中排名相邻的两个后缀也可能属于同一个字符串，因此将这两种情况除去后， $height$ 的最大值就是答案，判断两个后缀是否属于同一个字符串可以用下标以及两个字符串的长度来判断。

过题代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200000 + 100;
int len1, len2, ans;
int sa[maxn], rankk[maxn<<1], hei[maxn];
char str1[maxn], str2[maxn];
void get_sa_hei(char *s) {
    static int m[maxn], tmp[maxn], w[maxn];
    int len = strlen(s + 1);
    memset(rankk, 0, sizeof(rankk[0]) * (len * 2 + 2));
    for(int i = 0; i <= 255; ++i) w[i] = 0;
    for(int i = 1; i <= len; ++i) ++w[(int)s[i]];
    for(int i = 1; i <= 255; ++i) w[i] += w[i - 1];
    for(int i = len; i > 0; --i) tmp[w[(int)s[i]]--] = i;
    rankk[tmp[1]] = 1;
    for(int i = 2; i <= len; ++i)
        rankk[tmp[i]] = rankk[tmp[i - 1]] + (s[tmp[i]] != s[tmp[i - 1]]);
    for(int k = 1; k <= len; k <<= 1) {
        for(int i = 0; i <= len; ++i) w[i] = 0;
        for(int i = 1; i <= len; ++i) ++w[rankk[i + k]];
        for(int i = 1; i <= len; ++i) w[i] += w[i - 1];
        for(int i = len; i > 0; --i) m[w[rankk[i + k]]--] = i;
        for(int i = 0; i <= len; ++i) w[i] = 0;
        for(int i = 1; i <= len; ++i) ++w[rankk[i]];
        for(int i = 1; i <= len; ++i) w[i] += w[i - 1];
        for(int i = len; i > 0; --i) tmp[w[rankk[m[i]]]--] = m[i];
        m[tmp[1]] = 1;
        for(int i = 2; i <= len; ++i)
            m[tmp[i]] = m[tmp[i - 1]] +
                        (rankk[tmp[i]] != rankk[tmp[i - 1]]
                         || rankk[tmp[i] + k] != rankk[tmp[i - 1] + k]);
        for(int i = 0; i <= len; ++i) rankk[i] = m[i];
    }
    for(int i = 1; i <= len; ++i) sa[rankk[i]] = i;
    for(int i = 1,j = 0; i <= len; ++i) {
        if(rankk[i] == 1) continue;
        for(j? --j: 0; s[sa[rankk[i] - 1] + j] == s[i + j]; ++j);
        hei[rankk[i]] = j;
    }
}
int Get(int Index) {
    if(Index <= len1) {
        return 0;
    }
    return 1;
}
int main() {
    while(scanf("%s%s", str1 + 1, str2 + 1) != EOF) {
        ans = 0;
        len1 = strlen(str1 + 1);
        len2 = strlen(str2 + 1);
        str1[len1 + 1] = '$';
        str1[len1 + 2] = '\0';
        strcat(str1 + 1, str2 + 1);
        get_sa_hei(str1);
        for(int i = 2; i <= len1 + len2 + 1; ++i) {
            if(sa[i] == len1 + 1 || sa[i - 1] == len1 + 1) {
                continue;
            }
            if(Get(sa[i]) != Get(sa[i - 1])) {
                ans = max(ans, hei[i]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

E. Super Jumping! Jumping! Jumping

题意

在一个长度为 $n$ 的序列中，从 $start$ 点到 $end$ 点进行跳跃，只能从当前数字跳到下标大于当前位置且值也严格大于当前数字的位置，其中可以将 $start$ 点认为是无穷小，而 $end$ 点认为是无穷大，最终的得分为除了起点与终点，路径上所有数字的和，问得分最大为多少。

输入

多组输入，每组输入占一行，第一个数字为正整数 $n~(n\leq1000)$ ，接下去 $n$ 个整数，每个整数都在 $32$ 位整型范围内，当 $n=0$ 时输入停止。

输出

对于每组输入，输出最大的得分。

样例

输入
3 1 3 2 4 1 2 3 4 4 3 3 2 1 0
输出
4 10 3

题解

$dp[i]$ 表示以第 $i$ 个位置为最后一个点时，能够得到的最大分数，则该点可以从所有 $num[j]<num[i]~(j<i)$ 的位置转移过来，因此有如下状态转移：

$dp[i]=\max(dp[j]+num[i])~(j<i,num[j]<num[i])$

过题代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1000 + 100;
int n;
LL ans;
LL num[maxn], dp[maxn];
int main() {
    while(scanf("%d", &n), n != 0) {
        ans = -INF;
        for(int i = 1; i <= n; ++i) {
            scanf("%lld", &num[i]);
            dp[i] = num[i];
            for(int j = 1; j < i; ++j) {
                if(num[j] < num[i]) {
                    dp[i] = max(dp[i], dp[j] + num[i]);
                }
            }
            ans = max(ans, dp[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

F. Piggy-Bank

题意

完全背包。

输入

第一行为一个整数 $T$ ，接下来有 $T$ 组数据，每组数据第一行为两个整数 $E,F~(1\leq E\leq F\leq10000)$ ，分别表示空着的存钱罐与装满的存钱罐的重量，接下去一行为一个整数 $N~(1\leq N\leq500)$ ，表示有 $N$ 种货币，接下去 $N$ 行每行两个整数 $P,W~(1\leq P\leq50000,1\leq W\leq10000)$ ，分别表示每种货币的价值与重量，若不可能达到要求，则输出“不可能”。

输出

输出最少可能的货币的价值。

样例

输入
3 10 110 2 1 1 30 50 10 110 2 1 1 50 30 1 6 2 10 3 20 4
输出
The minimum amount of money in the piggy-bank is 60. The minimum amount of money in the piggy-bank is 100. This is impossible.

题解

完全背包， $F-E$ 作为背包容量，将所有值初始化为无穷大， $dp[0][0]$ 设为 $0$ ，最终若 $dp[n][F-E]$ 的值为无穷大，则表示无法达到，否则为答案。

过题代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 100000 + 100;
int T, n;
LL v, w, a, b, W;
LL dp[maxn];
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%lld%lld", &a, &b);
        W = b - a;
        scanf("%d", &n);
        memset(dp + 1, 0x3f, sizeof(LL) * W);
        for(int i = 1; i <= n; ++i) {
            scanf("%lld%lld", &v, &w);
            for(int j = w; j <= W; ++j) {
                dp[j] = min(dp[j], dp[j - w] + v);
            }
        }
        if(dp[W] == INF) {
            printf("This is impossible.\n");
        } else {
            printf("The minimum amount of money in the piggy-bank is %lld.\n", dp[W]);
        }
    }
    return 0;
}

G. 免费馅饼

题意

$t=0$ 时刻一个人站在位置 $x=5$ 处，他每秒只能移动 $1$ 米，在每个整数秒都可能在某个整数点位置掉下一些馅饼，若他处于 $x$ 处，则他在该时刻只能接住当前落在 $x$ 处的所有馅饼，问他最多能接住多少馅饼。

输入

多组输入，每组数据第一行为一个整数 $n~(0<n<100000)$ ，接下去 $n$ 行每行两个整数 $x,T~(0\leq x\leq10,0<T<100000)$ ，表示第 $T$ 秒有一个馅饼落在 $x$ 处，可能存在同一时刻同一地点落下多个馅饼的情况。 $n=0$ 表示输入结束。

输出

对于每组数据输出一个整数，表示能够接到的最多的馅饼数量。

样例

输入
6 5 1 4 1 6 1 7 2 7 2 8 3 0
输出
4

题解

用一个二维数组 $num[i][j]$ 记录在 $T$ 时刻 $x=j$ 处落下的馅饼数，则可以转化为数塔问题。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
struct Node {
    int x, T;
};
int n, MaxT, ans;
int l[maxn], r[maxn];
int dp[maxn][11], num[maxn][11];
Node node[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    for(int i = 0; i < maxn; ++i) {
        l[i] = max(0, 5 - i);
        r[i] = min(10, 5 + i);
    }
    while(scanf("%d", &n), n != 0) {
        ans = 0;
        MaxT = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &node[i].x, &node[i].T);
            ++num[node[i].T][node[i].x];
            MaxT = max(MaxT, node[i].T);
        }
        for(int i = 1; i <= MaxT; ++i) {
            for(int j = l[i]; j <= r[i]; ++j) {
                dp[i][j] = dp[i - 1][j];
                if(j - 1 >= 0) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
                }
                if(j + 1 <= 10) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j + 1]);
                }
                dp[i][j] += num[i][j];
            }
        }
        for(int i = 0; i <= 10; ++i) {
            ans = max(ans, dp[MaxT][i]);
        }
        printf("%d\n", ans);
        for(int i = 0; i < n; ++i) {
            num[node[i].T][node[i].x] = 0;
        }
    }
    return 0;
}

H. Tickets

题意

总共有 $K$ 个人排队买票，有两种买票方式，一种是每人各自买自己的票，另一种是相邻的两个人合起来一起买两张票，问所有人都买到票的最早的时间。

输入

第一行为一个整数 $N~(1\leq N\leq20)$ ，接下来有 $N$ 组数据，每组数据第一行为一个整数 $K~(1\leq K\leq2000)$ ，第二行为 $K$ 个整数 $S_i~(0\leq S_i\leq25)$ ，表示第 $i$ 个人单独买票需要的时间，第三行为 $K-1$ 个整数 $D_2,D_3,\cdots,D_K~(0\leq D_i\leq50)$ ，表示第 $i$ 个人与第 $i-1$ 个人一起买票需要的时间。

输出

对于每组数据，从 $08:00:00~am$ 开始计时，输出最早的卖完票的时间，格式为 HH:MM:SS am|pm。

样例

输入
2 2 20 25 40 1 8
输出
08:00:40 am 08:00:08 am

题解

$dp[i]$ 表示到第 $i$ 个人时最少需要的买票时间，则第 $i$ 个人要么自己买，要么和第 $i-1$ 个人一起买，因此有如下状态转移方程：

$dp[i]=\min(dp[i-1]+S[i],dp[i-2]+D[i])$

最大可能的答案为 $2000\times25=5\times10^4~s$ ，加上 $08:00:00~am$ 不会超过 $24$ 小时，因此不必考虑第二天的问题，注意这里中午 $12$ 点整的表示为： $00:00:00~pm$ 。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
using namespace std;
#define LL long long
const int maxn = 2000 + 100;
int T, n, ans;
int s[maxn], d[maxn], dp[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &s[i]);
        }
        for(int i = 2; i <= n; ++i) {
            scanf("%d", &d[i]);
        }
        dp[1] = s[1];
        for(int i = 2; i <= n; ++i) {
            dp[i] = min(dp[i - 1] + s[i], dp[i - 2] + d[i]);
        }
        ans = dp[n] + 8 * 3600;
        printf("%02d:%02d:%02d %cm\n", ans / 3600 % 12, ans / 60 % 60, ans % 60, ans >= 12 * 3600? 'p': 'a');
    }
    return 0;
}

I. 最少拦截系统

题意

如题。

输入

输入若干组数据.每组数据包括：导弹总个数（正整数），导弹依此飞来的高度（雷达给出的高度数据是不大于 $30000$ 的正整数，用空格分隔）。

输出

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例

输入
8 389 207 155 300 299 170 158 65
输出
2

题解

用一个数组储存当前所有导弹拦截系统能拦截导弹的最低高度，最开始该数组为空，从左往右遍历每个数字，每当出现一个新的数字时，从数组中贪心地找出大于等于当前高度的最小数字，用这个数字替换找到的数字，表示用该系统拦截当前高度的导弹，如果无法找到，则将当前数字添加到数组中，由于维护一个有序数组可以通过二分查找降低时间复杂度，因此本题的写法可以与最长上升子序列的 $O(n\log n)$ 写法完全一致，是不是很像 HDU 1051 Wooden Sticks？是的这题的正解是贪心不是 $dp$ ，只是写法一模一样而已，从证明的角度来说，只能用贪心证明。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
using namespace std;
#define LL long long
const int maxn = 2000 + 100;
int T, n, ans;
int s[maxn], d[maxn], dp[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &s[i]);
        }
        for(int i = 2; i <= n; ++i) {
            scanf("%d", &d[i]);
        }
        dp[1] = s[1];
        for(int i = 2; i <= n; ++i) {
            dp[i] = min(dp[i - 1] + s[i], dp[i - 2] + d[i]);
        }
        ans = dp[n] + 8 * 3600;
        printf("%02d:%02d:%02d %cm\n", ans / 3600 % 12, ans / 60 % 60, ans % 60, ans >= 12 * 3600? 'p': 'a');
    }
    return 0;
}

J. 爬楼梯

题意

如题。

输入

第一行只有一个整数 $T~(1\leq T\leq45)$ ，表示数据组数。下面的 $T$ 行每一行有一个整数 $n~(1\leq n\leq45)$ ，表示有多少级楼梯。

输出

对于每一组数据输出一个整数 $s$ ，表示方案数。

样例

输入
4 1 2 3 4
输出
1 2 3 5

题解

斐波那契数列预处理。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
using namespace std;
#define LL long long
const int maxn = 100;
int T, n;
LL dp[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i < maxn; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        printf("%I64d\n", dp[n]);
    }
    return 0;
}

K. 饭卡

题意

如题。

输入

多组数据。对于每组数据：第一行为正整数 $n~(n\leq1000)$ ，表示菜的数量。第二行包括 $n$ 个正整数，表示每种菜的价格，价格不超过 $50$ 。第三行包括一个正整数 $m~(m\leq1000)$ ，表示卡上的余额。 $n=0$ 表示数据结束。

输出

对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。

样例

输入
1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0
输出
-45 32

题解

用 $dp[i][j]$ 表示用前 $i$ 种菜，能否凑出 $j$ 元钱，且必须保证前 $i-1$ 种菜凑出的总价值小于等于 $m-5$ ，若能凑出，则 $dp[i][j]=true$ ，否则为 $false$ ，则类似于 $01$ 背包可以得出以下递推公式：

$dp[i][j] = dp[i-1][j]~or~dp[i-1][j - w[i]]\quad\quad(j-w[i]\leq m-5)$
所有能够凑出的最大价值可能达到 $m-5+\max(w[i])$ ，因此要注意 $dp$ 转移过程中的下标范围，初始值为：

$dp[i][j]= \begin{cases} true&(i=0,j=0)\\ false&others \end{cases}$
最后，需要注意要贪心地从价值小的菜价到价值大的菜价进行 $dp$ 才能尽可能地凑出多种价值，贪心证明与数的二进制表示从大到小贪心同理。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
int n, m, ans;
bool dp[maxn];
int w[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n), n != 0) {
        ans = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &w[i]);
        }
        sort(w, w + n);
        scanf("%d", &m);
        memset(dp, 0, sizeof(dp));
        dp[0] = true;
        for(int i = 0; i < n; ++i) {
            for(int j = maxn - 1; j >= w[i]; --j) {
                if(j - w[i] <= m - 5) {
                    dp[j] = (dp[j] || dp[j - w[i]]);
                    if(dp[j]) {
                        ans = max(ans, j);
                    }
                }
            }
        }
        printf("%d\n", m - ans);
    }
    return 0;
}

L. 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

题意

多重背包。

输入

输入数据首先包含一个正整数 $C$ ，表示有 $C$ 组测试用例，每组测试用例的第一行是两个整数 $n$ 和 $m~(1\leq n\leq100,1\leq m\leq100)$ ，分别表示经费的金额和大米的种类，然后是 $m$ 行数据，每行包含 $3$ 个数 $p,h,c~(1\leq p\leq20,1\leq h\leq200,1\leq c\leq20)$ ，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。

输出

对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。

样例

输入
1 8 2 2 100 4 4 100 2
输出
400

题解

数据范围太小以至于用 $01$ 背包暴力也能过，正解是多重背包。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <ctime>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
struct Node {
    int v, w;
    Node() {}
    Node(int ww, int vv) {
        v = vv;
        w = ww;
    }
};
int T, n, m, cnt, p, h, c;
Node node[maxn];
int dp[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        cnt = 0;
        scanf("%d%d", &m, &n);
        memset(dp, 0, sizeof(int) * (m + 1));
        for(int i = 0; i < n; ++i) {
            scanf("%d%d%d", &p, &h, &c);
            for(int j = 0; j < 5; ++j) {
                if(c - (1 << j) <= 0) {
                    break;
                }
                c -= (1 << j);
                node[cnt++] = Node(p * (1 << j), h * (1 << j));
            }
            node[cnt++] = Node(p * c, h * c);
        }
        for(int i = 0; i < cnt; ++i) {
            for(int j = m; j >= node[i].w; --j) {
                dp[j] = max(dp[j], dp[j - node[i].w] + node[i].v);
            }
        }
        printf("%d\n", dp[m]);
    }
    return 0;
}