马上就要NOIP了，我才发现我在DP方面还算是个小白，简直害怕。所以这两天在恶补DP，希望还有补救的机会……【哭】
首先，搞了一发数字三角形……
题目描述 Description
如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。
输入描述 Input Description
第一行是数塔层数N(1<=N<=100)。
第二行起，按数塔图形，有一个或多个的整数，表示该层节点的值，共有N行。
输出描述 Output Description
输出最大值
样例输入 Sample Input
5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11
样例输出 Sample Output
86
逆推上去资瓷啊！
for(int i = 1; i <= n; i++) dp[n][i] = num[n][i]; for(int i = n - 1; i >= 1; i--) for(int j = 1; j <= i; j++) dp[i][j] = num[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);然后，搞了一发LIS问题……写了个O(nlogn)的做法。
for(int i = 1; i <= n; i++) { int pos = lower_bound(G + 1, G + 1 + n, num[i]) - G; G[pos] = num[i]; dp[i] = pos; }不过要记得G数组初始值要设为INT_MAX
LIS之后，应运而生的当然是LCS问题233
for(int i = 1; i <= len1; i++) for(int j = 1; j <= len2; j++) { if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); else dp[i][j] = max(dp[i - 1][j - 1] + 1, max(dp[i - 1][j], dp[i][j - 1])); }然后背包？ 说着又写了个01背包——采药……
for(int i = 1; i <= m; i++) for(int j = t; j>= 0; j--) { dp[i][j] = dp[i - 1][j]; if(j - p[i].t >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - p[i].t] + p[i].w); }无良出题人卡空间？滚动数组优化！
for(int i = 1; i <= m; i++) for(int j = T; j >= p[i].t; j--) dp[j] = max(dp[j], dp[j - p[i].t] + p[i].w);01背包之后，完全背包？ 又是一发采药233……不过是有区别的
题目背景
此题为NOIP2005普及组第三题的疯狂版。
此题为纪念LiYuxiang而生。
题目描述
LiYuxiang是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是LiYuxiang，你能完成这个任务吗？
此题和原题的不同点：
1.每种采药可以无限制地疯狂采摘。
2.药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！
输入输出格式
输入格式： 输入第一行有两个整数T（1 <= T <= 100000）和M（1 <= M <= 10000），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到10000之间（包括1和10000）的整数，分别表示采摘某种草药的时间和这种草药的价值。
输出格式： 输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
输入输出样例
输入样例#1： 70 3 71 100 69 1 1 2
输出样例#1：
140
说明
对于30%的数据，M <= 1000；
对于全部的数据，M <= 10000，且M*T<10000000(别数了，7个0)。
加油LiYuxiang，第一个AC留给你！
把01背包的第二个for循环反过来写不就好了吗？！
for(int i = 1; i <= m; i++) for(int j = p[i].t; j <= T; j++) dp[j] = max(dp[j], dp[j - p[i].t] + p[i].w);基础DP就这些？当然不是！不过……就先写到这里吧。
转载于:https://www.cnblogs.com/Loi-Vampire/p/6017039.html
