知识总结

动态规划（DP）的学术定义在这里不谈，我在这里只讲我们该怎么做题。
首先，学DP不就是刷题嘛。
这个寒假做了60道左右的DP题目，听了N节DP课，对DP解题有了初步的能力。
DP本身是没有精确的细分方法的，但是为了学习和交流的方便，我们把DP题目分为如下几类：

1、线性dp
2、背包问题
3、区间dp
4、树形dp
5、换根dp
6、状压dp
7、概率dp
8、期望dp
9、数位dp
10、虚树dp
11、斜率优化
12、单调队列优化
13、插头dp
14、凸优化dp
15、四边形不等式（决策单调性优化）

以上15种DP问题，每一类都需要进行深度理解和充分训练，个人建议是一类题至少练10道不同考法的题目。
对于所有的DP问题，有一种通用的分析方法(学自Acwing的y总)，即集合划分法：
以01背包问题为例，我们可以把f[i][j]定义为在前i个物品中选，重量总和不超过j的所有选法，所构成的集合。
背包问题的集合只有三种属性: 最大值，最小值，(方案)个数
然后我们就可以对集合进行划分，一般是以最后一个不同点进行划分。在这里，就是选的最后一个物品。
若不选最后一个物品，则状态为f[i-1][j]，我们可以推出f[i][j] = f[i-1][j]；
若选择最后一个物品，则状态为f[i-1][j-v[i]]，可以推出f[i][j] = f[i-1][j-v[i]]+w[i]。
其它点众所周知就不细说了。
但有两点必须要指出来：
第一，集合的划分其实是任意的，怎么好算怎么划分，同一道题也可以有N种划分方法。也就是说，不要死背那些背包的状态表示，要用集合的角度去看待题目。比如背包问题一般就是，第一维表示物品选择，后面几个维度用来描述限制。
第二，虽然我们可以进行降维优化，但是写状态转移方程的时候，必须写全部维度，不然几乎无法思考！！！

习题题解

A.送快弟

题目链接
思路:
01背包板子
代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
	int t;
	scanf("%d", &t);
	
	while(t--) 
	{
		scanf("%d%d", &n, &m);
		memset(f, 0, sizeof f);
		
		for(int i=1; i<=n; ++i)
			scanf("%d", &w[i]);
		for(int i=1; i<=n; ++i)
			scanf("%d", &v[i]); 
		
		for(int i=1; i<=n; ++i)
		{
			for(int j=0; j<=m; ++j)
			{
				f[i][j] = f[i-1][j];
				if(j>=v[i]) 
				f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);
			}
		}
		printf("%d\n", f[n][m]);
	}
	
	
	return 0;
}

B.CD

题目链接

解题思路:
01背包求方案板子题，逆序dp，正序枚举输出方案。

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 22, M = 10010;

int n, m;
int v[N], w[N];
int f[N][M];

int main()
{
	while(~scanf("%d%d", &m, &n))
	{
		memset(f, 0, sizeof f);
		
		for(int i=1; i<=n; ++i)
		{
			scanf("%d", &v[i]);
			w[i] = v[i];
		}
		
		for(int i=n; i>=1; --i)
		{
			for(int j=0; j<=m; ++j)
			{
				f[i][j] = f[i+1][j];
				if(j>=v[i])
					f[i][j] = max(f[i][j], f[i+1][j-v[i]]+w[i]);
			}
		}
		int j = m;
		for(int i=1; i<=n; ++i)
		{
			if(f[i][j] == f[i+1][j-v[i]]+w[i])
			{
				printf("%d ", v[i]);
				j-=v[i];
			}
		}
		printf("sum:%d\n", f[1][m]);
	}
	
	
	return 0;
}