动态规划

闫氏DP分析法

1.数字三角形模型

1.1只取一条最大路或最小路

1015. 摘花生
只能向下或向右走，求最大能取多少花生
记录每个点最大能取到多少花生，从左上一直推到右下角
\(dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]\)

复杂度：\(O(tn^2)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 101;
int dp[MAXN][MAXN];
int a[MAXN][MAXN];
int main()
{
	int t;cin >> t;
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		int r,c;cin >> r >> c;
		for(int i = 1;i <= r;i++)
		for(int j = 1;j <= c;j++)
			cin >> a[i][j];
		dp[1][1] = a[1][1];
		for(int i = 3;i <= r + c;i++)//从小到大枚举步数
		{
			for(int _i = 1;_i <= r;_i++)
			{
				int _j = i - _i;
				if(_j <= 0 || _j > c)
					continue;
				else
				{
					if(_i != 1)
						dp[_i][_j] = dp[_i - 1][_j];
					if(_j != 1)
						dp[_i][_j] = max(dp[_i][_j],dp[_i][_j - 1]);
					dp[_i][_j] += a[_i][_j];
				}
			}
		}
		cout << dp[r][c] << endl;
	}
}

1018. 最低通行费
同上，只是取最小值
\(dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j]\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 10;
int dp[MAXN][MAXN];
int main()
{
	int n;cin >> n;
	for(int i = 1;i <= n;i++)
	for(int j = 1;j <= n;j++)
	cin >> dp[i][j];
	for(int i = 3;i <= n*2;i++)
	{
		for(int _i = 1;_i <= n;_i++)
		{
			int _j = i - _i;
			if(_j <= 0 || _j > n)
				continue;
			int mi = 1e9 + 10;
			if(_j - 1 > 0)
				mi = min(mi,dp[_i][_j - 1]);
			if(_i - 1 > 0)
				mi = min(mi,dp[_i - 1][_j]);
			dp[_i][_j] += mi;
		}
	}
	cout << dp[n][n];
}

1.2取两条路，可重叠

1027.方格取数
取两条路得到最大值，我们就让两条路同时走，如果走到同一个格子就加一次
复杂度：\(O(n^3)\)

#include<bits/stdc++.h>
using namespace std;
int dp[11][11][22];
int a[11][11];
int main()
{
	int n;cin >> n;
	int i,j,v;cin >> i >> j >> v;
	while(i != 0)
	{
		a[i][j] = v;
		cin >> i >> j >> v;
	}
	dp[1][1][2] = a[1][1];
	for(int i = 3;i <= n*2;i++)//枚举两条路的步数
	{
		for(int i1 = 1;i1 <= n;i1++)//枚举第一条路线的i
		{
			int j1 = i - i1;
			if(j1 <= 0 || j1 > n)
				continue;
			for(int i2 = 1;i2 <= n;i2++)//枚举第二条
			{
				int j2 = i - i2;
				if(j2 <= 0 || j2 > n)
					continue;
				int w = a[i1][j1] + a[i2][j2];
				if(i1 == i2)//走到同一个格子
					w -= a[i1][j1];
				int ma = 0;
				if(i1 - 1 > 0 && i2 - 1 > 0)
					ma = dp[i1 - 1][i2 - 1][i - 1];
				if(i1 - 1 > 0 && j2 - 1 > 0)
					ma = max(ma,dp[i1 - 1][i2][i - 1]);
				if(j1 - 1 > 0 && i2 - 1 > 0)
					ma = max(ma,dp[i1][i2 - 1][i - 1]);
				if(j1 - 1 > 0 && j2 - 1 > 0)
					ma = max(ma,dp[i1][i2][i - 1]);
				dp[i1][i2][i] = ma + w;
			}
		}
	}
	cout << dp[n][n][n*2];
}

1.3取两条路，不可重叠

275. 传纸条
那就默认让一条路的\(i1\)大于\(i2\)即可，这样两条路就没有相交点
复杂度：\(O(n^3)\)

#include<bits/stdc++.h>
using namespace std;//假设第一条路径就是高于第二条路径
int a[51][51];
int dp[51][51][102];
int main()
{
	int m,n;cin >> m >> n;
	for(int i = 1;i <= m;i++)
	for(int j = 1;j <= n;j++)
		cin >> a[i][j];
	for(int i = 1;i <= m + n;i++)//枚举步数
	{
		for(int i1 = 1;i1 <= m;i1++)
		{
			int j1 = i - i1;
			if(j1 <= 0 || j1 > n)
				continue;
			for(int i2 = 1;i2 < i1;i2++)
			{
				int j2 = i - i2;
				if(j2 <= 0 || j2 > n)
					continue;
				int ma = 0;
				if(i1 - 1 > 0 && i2 - 1 > 0)
					ma = dp[i1 - 1][i2 - 1][i - 1];
				if(i1 - 1 > 0 && j2 - 1 > 0)
					ma = max(ma,dp[i1 - 1][i2][i - 1]);
				if(j1 - 1 > 0 && i2 - 1 > 0)
					ma = max(ma,dp[i1][i2 - 1][i - 1]);
				if(j1 - 1 > 0 && j2 - 1 > 0)
					ma = max(ma,dp[i1][i2][i - 1]);
				dp[i1][i2][i] = ma + a[i1][j1] + a[i2][j2];
			}
		}
	}
	cout << dp[m][m - 1][n + m - 1];
}

2.最长上升子序列模型

2.1求最长长度

1017. 怪盗基德的滑翔翼
1.贪心法：如果大于最后一个数，就直接加入，否则找第一个大于它的数替换，这样就实现了让后面有潜力的子序列能替换掉最大串
复杂度：\(O(nlog_2n)\)

#include<bits/stdc++.h>
using namespace std;
int a[101],b[101],c[101];
int main()
{
	int k;cin >> k;
	while(k--)
	{
		int n;cin >> n;
		int ptop = 1;
		cin >> a[1];
		c[1] = a[1];
		for(int i = 2;i <= n;i++)
		{
			int x;cin >> c[i];
			x = c[i];
			if(a[ptop] < x)
				a[++ptop] = x;
			else
				a[lower_bound(a + 1,a + 1 + ptop,x) - a] = x;
		}
		int pptop = 1;
		b[1] = c[n];
		for(int i = n - 1;i >= 1;i--)
		{
			int x = c[i];
			if(b[pptop] < x)
				b[++pptop] = x;
			else
				b[lower_bound(b + 1,b + 1 + pptop,x) - b] = x;
		}
		cout << max(ptop,pptop) << endl;
	}
}

2.动态规划：存这个位置最长的串，从前往后枚举，每次都向前找最长的能插上的位置然后加1
复杂度：\(O(n^2)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 101;
int a[MAXN],dp[MAXN];
int main()
{
	int k;cin >> k;
	while(k--)
	{
		int n;cin >> n;
		memset(dp,0,sizeof(dp));
		int ma = 0;
		a[0] = 10001;
		for(int i = 1;i <= n;i++)
			cin >> a[i];
		for(int i = 1;i <= n;i++)
		for(int j = 0;j < i;j++)
		if(a[j] > a[i])
		{
			dp[i] = max(dp[j] + 1,dp[i]);
			ma = max(dp[i],ma);
		}
		memset(dp,0,sizeof(dp));
		a[n + 1] = 10001;
		for(int i = n;i >= 1;i--)
		for(int j = i + 1;j <= n + 1;j++)
		if(a[j] > a[i])
		{
			dp[i] = max(dp[j] + 1,dp[i]);
			ma = max(dp[i],ma);
		}
		cout << ma << endl;
	}
}

2.2求最长山形

1014. 登山
482. 合唱队形
从前往后和从后往前都求一遍，求最大和
贪心法：复杂度\(O(nlog_{2}n)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
int a[MAXN];
int b[MAXN],ans[MAXN];
int main()
{
	int n;cin >> n;
	int ptop = 1;
	cin >> a[1];
	b[1] = a[1];
	ans[1] = 1;
	for(int i = 2;i <= n;i++)
	{
		cin >> a[i];
		int x = a[i];
		if(x > b[ptop])
			b[++ptop] = x;
		else
			b[lower_bound(b + 1,b + 1 + ptop,x) - b] = x;
		ans[i] = ptop;
	}
	ptop = 1;
	b[1] = a[n];
	int ma = ans[n];
	for(int i = n - 1;i >= 1;i--)
	{
		int x = a[i];
		if(x > b[ptop])
			b[++ptop] = x;
		else
			b[lower_bound(b + 1,b + 1 + ptop,x) - b] = x;
		ma = max(ptop + ans[i] - 1,ma);
	}
	cout << ma;
}

2.3引索型最长子序列

1012. 友好城市
\(a_i\)和\(b_i\)都要递增
对\(a_i\)排序，对排序后的\(b_i\)做最长子序列
复杂度：\(O(nlog_2n)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 10;
pair<int,int> pa[MAXN];
int b[MAXN];
int main()
{
	int n;cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> pa[i].first >> pa[i].second;
	sort(pa + 1,pa + 1 + n);
	b[1] = pa[1].second;
	int ptop = 1;
	for(int i = 2;i <= n;i++)
		if(pa[i].second > b[ptop])
			b[++ptop] = pa[i].second;
		else
			b[lower_bound(b + 1,b + 1 + ptop,pa[i].second) - b] = pa[i].second;
	cout << ptop;
}

2.4最少递增序列

1010. 拦截导弹
给一个序列，将其分成多个单调递增序列，求最少数量
记录每个序列的最大值，枚举放下，如果放不下就增加一个序列来放
复杂度：\(O(nlog_2n)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
int a[MAXN],b[MAXN],c[MAXN];
int main()
{
	int ptop = 0;
	int x,ma = 0;
	while(scanf("%d",&x) != EOF)
	{
		a[++ptop] = x;
	}
	int pptop = 1;c[1] = b[1] = a[ptop];
	int ans = 1;
	for(int i = ptop - 1;i >= 1;i--)
	{
		int x = a[i];
		int aim = lower_bound(c + 1,c + 1 + ans,x,[&](int a,int b){
			return a > b;
		}) - c;
		if(aim == ans + 1)
			c[++ans] = x;
		else
			c[aim] = x;
		if(b[pptop] <= x)
		{
			b[++pptop] = x;
		}
		else
		{
			b[upper_bound(b + 1,b + 1 + pptop,x) - b] = x;
		}
	}
	cout << pptop << endl << ans << endl;
}

2.5求最大的上升子序列

1016. 最大上升子序列和
动态规划暴力，找前面最大的可以放在后面的，就是把记录的长度换成总和，没有贪心做法
复杂度：\(O(n^2)\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10,MAX = 1e4 + 10;
int a[MAXN];
int dp[MAX];
int main()
{
	int n;cin >> n;
	for(int i = 1;i <= n;i++)
	{
		int x;cin >> x;
		int ma = 0;
		for(int i = 1;i < x;i++)
		{
			ma = max(ma,dp[i]);
		}
		dp[x] = ma + x;
	}
	int ma = 0;
	for(int i = 1;i <= MAX - 1;i++)
		ma = max(ma,dp[i]);
	cout << ma << endl;
}

2.6最少分割单调子序列

187. 导弹防御系统
爆搜
枚举每个位置是加入递增还是递减，然后深度优先搜索，得出一个答案，回溯然后用这个答案剪枝
复杂度：\(O(n2^n)\)

#include<bits/stdc++.h>
using namespace std;
int a[51];
int ans = 999;
int ma[52];
int mi[52];
int n;
void dfs(int i,int ptop1,int ptop2){
	if(ptop1 + ptop2 >= ans) return;
	if(i == n + 1) ans = ptop1 + ptop2;
	else{
		int j;
		for(j = 1;j <= ptop1;j++)
			if(a[i] > ma[j])
				break;
		int pre = ma[j];
		ma[j] = a[i];
		if(j == ptop1 + 1)
			dfs(i + 1,ptop1 + 1,ptop2);
		else
			dfs(i + 1,ptop1,ptop2);
		ma[j] = pre;
		for(j = 1;j <= ptop2;j++)
			if(a[i] < mi[j])
				break;
		pre = mi[j];
		mi[j] = a[i];
		if(j == ptop2 + 1)
			dfs(i + 1,ptop1,ptop2 + 1);
		else
			dfs(i + 1,ptop1,ptop2);
		mi[j] = pre;
	}
}
int main()
{
	cin >> n;
	while(n != 0){
		ans = 999;
		for(int i = 1;i <= n;i++)
			cin >> a[i];
		dfs(1,0,0);
		cout << ans << endl;
		cin >> n;
	}
}

2.7最长公共上升子序列

如果\(a[i]=b[j]\)，那么如果要接上这个，就要找前面最长的还小于它们的公共上升子序列，用\(f[i][j]\)来表示以\(b[j]\)结尾的最长公共上升子序列，要找的就是\(f_{max}[i'][j'](b[j']<a[j]\&\&j'<j)\)

for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
{
    if(a[i] == b[j]){
        int ma = 1;
        for(int k = 1;k < j;k++)
            if(a[i] > b[j])
            	ma = max(dp[i][k] + 1,ma);
        dp[i][j] = ma;
    }
}

三重循环会爆时间，因此要简化，我们可以看到\(j\)是递增的，而\(k\)循环是找\(j\)之前的东西，所以我们只要在\(j\)循环内找即可，推一个\(j\)找一次

for(int i = 1;i <= n;i++)
{
    int ma = 1;
    for(int j = 1;j <= n;j++)
    {
        if(a[i] == b[j]) dp[i][j] = ma;
        else if(a[i] > b[j]) ma = max(dp[i][j] + 1,ma);
    }
}

综上所述
复杂度：\(O(n^2)\)

#include<bits/stdc++.h>
using namespace std;
int dp[3001][3001];
int a[3001],b[3001];
int main()
{
	int n;cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	for(int i = 1;i <= n;i++)
		cin >> b[i];
	for(int i = 1;i <= n;i++)
	{
		int ma = 1;
		for(int j = 1;j <= n;j++)//从前往后,尝试加入a[i]
		{
			dp[i][j] = dp[i - 1][j];
			if(a[i] == b[j])//尝试加入
			dp[i][j] = max(dp[i][j],ma);
			else if(a[i] > b[j])
			ma = max(dp[i][j] + 1,ma);
		}
	}
	int ma = 0;
	for(int i = 1;i <= n;i++)
		ma = max(dp[n][i],ma);
	cout << ma << endl;
}

addtion 2.8最长下降子序列及计不同序列数量

G - 低价购买
用dp来做最长下降子序列，每次得到一个数就向前找比它大的然后尝试接上
计数时有可能重复计数，那么我们取一个数是如果前面有相同的数，那么就把那个数抛弃掉，因为对后面的数来说接前面的数还是这个数都一样并且接后面的那个相同的数更有可能更长

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;

pair<int,int> dp[N];
int a[N];

int main()
{
	int n;cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	int ma = 0;
	for(int i = 1;i <= n;i++){
		dp[i] = {1,1};
		for(int j = i - 1;j >= 1;j--){
			if(a[i] < a[j]){
				if(dp[j].first + 1 > dp[i].first){
					dp[i].first = dp[j].first + 1;
					dp[i].second = dp[j].second;
				}else if(dp[j].first + 1 == dp[i].first)
					dp[i].second += dp[j].second;
			}else if(a[i] == a[j])
				dp[j] = {0,0};
		}
		ma = max(ma,dp[i].first);
	}
	int cnt = 0;
	for(int i = 1;i <= n;i++)
		if(ma == dp[i].first)
			cnt += dp[i].second;
	cout << ma << ' ' << cnt << endl;
}

3.背包模型

3.1 01背包问题

423. 采药
枚举物品，每次尝试放入物品，如果放入后状态更好就替换，否则不换\(dp[i][j]=max(dp[i-1][j - t]+v,dp[i-1][j])\)
如果从后往前更新，就不会产生一个物品取两次的情况了，所以有\(dp[j]=max(dp[j-t]+v,dp[j])\)
时间复杂度：\(O(tm)\)
开\(dp[][]\)

#include<bits/stdc++.h>
using namespace std;
int dp[101][1001];
int main()
{
	int t,m;cin >> t >> m;
	for(int i = 1;i <= m;i++){
		
		int tt,v;cin >> tt >> v;
		for(int j = 1;j <= t;j++)
			if(j - tt >= 0)
				dp[i][j] = max(dp[i - 1][j - tt] + v,dp[i - 1][j]);
			else
				dp[i][j] = dp[i - 1][j];
	}
	cout << dp[m][t];
}

开\(dp[]\)

#include<bits/stdc++.h>
using namespace std;
int dp[1001];
int main()
{
		int t,m;cin >> t >> m;
		for(int i = 1;i <= m;i++){
			int tt,v;cin >> tt >> v;
			for(int j = t;j >= tt;j--)
				dp[j] = max(dp[j - tt] + v,dp[j]);
		}
		cout << dp[t] << endl;
}

1024. 装箱问题
只有已经被标记过的体积才能再填充减去再标记，最后找最小标记即可

#include<bits/stdc++.h>
using namespace std;
const int MAXV = 2e4 + 10;
bool dp[MAXV];
int main()
{
	int mi = MAXV;
	int v,n;cin >> v >> n;
	dp[v] = 1;
	for(int i = 1;i <= n;i++){
		int vv;cin >> vv;
		for(int j = vv;j <= v;j++)
			if(dp[j])
			{
				dp[j - vv] = 1;
				mi = min(j - vv,mi);
			}
	}
	cout << mi;
}

3.2二重01背包问题

1022. 宠物小精灵之收服
两个限制条件，就是加一重循环来更新，用两个数值代表现在状态
\(dp[i][j]=max(dp[i][j],dp[i-t_1][j-t_2]+v)\)
时间复杂度：\(O(nmk)\)

#include<bits/stdc++.h>
using namespace std;
pair<int,int> ans;
int dp[1001][501];
int main()
{
	int n,m,k;cin >> n >> m >> k;
	ans.first = 0,ans.second = m;
	for(int i = 1;i <= k;i++){
		int nu,at;cin >> nu >> at;
		for(int _i = 0;_i <= n - nu;_i++)
		for(int _j = 1;_j <= m - at;_j++)
		{
			dp[_i][_j] = max(dp[_i][_j],dp[_i + nu][_j + at] + 1);
			if(dp[_i][_j] > ans.first)
				ans = {dp[_i][_j],_i};
			else if(dp[_i][_j] == ans.first)
				ans.second = max(_j,ans.second);
		}
	}
	cout << ans.first << ' ' << ans.second;
}

3.3 01背包状态出现次数

278. 数字组合
设初始状态出现次数为1，更新背包时把更新前的出现次数加在更新后状态的出现次数

#include<bits/stdc++.h>
using namespace std;
int dp[10001];//出现次数
int main()
{
	int n,m;cin >> n >> m;
	dp[0] = 1;
	for(int i = 1;i <= n;i++){
		int x;cin >> x;
		for(int i = m;i >= x;i--)
			dp[i] += dp[i - x];
	}
	cout << dp[m];
}

3.4完全背包求方案数

1023. 买书
从前往后更新背包，这样就是完全背包，因为更新背包是更新后面，可以继续更新

#include<bits/stdc++.h>
using namespace std;
int dp[1001];//出现此数的数量
int num[] = {10,20,50,100};
int main()
{
	int n;cin >> n;
	dp[0] = 1;
	for(int i = 0;i < 4;i++)
	    for(int j = num[i];j <= n;j++)
	        dp[j] += dp[j - num[i]];
	cout << dp[n];
}

1021. 货币系统同理，记得开long long

3.5最少的数来组合出所有数

532. 货币系统
从小的开始，如果这个被标记过，就说明已经被其他数给表示了，否则就加入，进行一次完全背包

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 101,MAXM = 2.5e4;
bool dp[MAXM];
int a[MAXN];
int main()
{
	int t;cin >> t;
	while(t--){
		int n;cin >> n;
		memset(dp,0,sizeof(dp));
		dp[0] = 1;
		for(int i = 1;i <= n;i++)
			cin >> a[i];
		sort(a + 1,a + 1 + n);
		int ans = 0;
		for(int i = 1;i <= n;i++){
			if(dp[a[i]])
				continue;
			ans++;
			for(int j = 0;j <= a[n] - a[i];j++)
				if(dp[j])
					dp[j + a[i]] = 1;
		}
		cout << ans << endl;
	}
}

3.6单调队列+滑动窗口+滚动数组优化多重完全背包

6. 多重背包问题 III
现加入s个价值为w，体积为v的物体，那么能更新位置x的有

\[dp[i][x]=max(dp[i-1][x],dp[i-1][x-v]+w,dp[i-1][x-2v]+2w...,dp[i-1][x-sv]+sw) \]

那么更新位置x+v有

\[dp[i][x+v]=max(dp[i-1][x+v],dp[i-1][x]+w,dp[i-1][x-v]+w...,dp[i-1][x-(s-1)v]+(s-1)w) \]

可以见到形式十分相似，我们可以使用滑动窗口来维护这个式子，利用单调队列来求出这个的最大值
枚举所有v的余数即可

#include<bits/stdc++.h>
using namespace std;
const int MAXV = 2e4 + 10;
int dp[2][MAXV];
pair<int,int> deq[MAXV];
int main()
{
	int n,op = 0,V;cin >> n >> V;
	for(int i = 1;i <= n;i++){
		int v,w,s;cin >> v >> w >> s;
		
		for(int j = 0;j < v;j++)//枚举余数
		{
			int top = 1,end = 1;
			deq[1] = {0,0};
			for(int k = 1;k*v + j <= V;k++){
				while(top <= end && deq[end].first + (k - deq[end].second)*w < dp[1 - op][k*v + j])
					end--;
				deq[++end] = {dp[1 - op][k*v + j],k};
				if(k - deq[top].second > s)
					top++;
				dp[op][k*v + j] = deq[top].first + (k - deq[top].second)*w;
			}
		}
		op = 1 - op;
	}
	cout << dp[1 - op][V];
}

3.7简单的混合背包

7. 混合背包问题
如果是一次，就从后往前进行一次
如果是完全就从前往后更新
如果是多重就判断给的大小是否超过背包大小，如果超过就继续完全背包，否则就执行s次01背包

#include<bits/stdc++.h>
using namespace std;
int dp[1001];
int main()
{
	int n,V;cin >> n >> V;
	for(int i = 1;i <= n;i++){
		int v,w,s;cin >> v >> w >> s;
		if(s == 0 || v*s >= V){
			for(int k = v;k <= V;k++)
				dp[k] = max(dp[k],dp[k - v] + w);
		}
		else
		{
			s = max(s,1);
			for(int j = 1;j <= s;j++)
				for(int k = V;k >= v;k--)
					dp[k] = max(dp[k],dp[k - v] + w);
		}
	}
	cout << dp[V];
}

3.8二维费用背包

8. 二维费用的背包问题
就是加了1维，没什么差别

#include<bits/stdc++.h>
using namespace std;
int dp[101][101];
int main()
{
	int n,V,M;cin >> n >> V >> M;
	for(int i = 1;i <= n;i++){
		int v,m,w;cin >> v >> m >> w;
		for(int j = V;j >= v;j--)
		for(int k = M;k >= m;k--)
			dp[j][k] = max(dp[j][k],dp[j - v][k - m] + w);
	}
	cout << dp[V][M];
}

3.9满足条件或更好的最值背包

1020. 潜水员
每次找最优能更新此位置的位置

#include<bits/stdc++.h>
using namespace std;
int dp[80][22];
int main()
{
	int m,n;cin >> m >> n;
	int t;cin >> t;
	for(int i = 0;i <= m;i++)
	for(int j = 0;j <= n;j++)
		dp[j][i] = 1e9 + 10;
	dp[0][0] = 0;
	for(int i = 1;i <= t;i++){
		int a,b,c;cin >> a >> b >> c;
		for(int j = n;j >= 0;j--)
		for(int k = m;k >= 0;k--)
		{
			int aimj = max(0,j-b),aimk = max(0,k-a);
			dp[j][k] = min(dp[j][k],dp[aimj][aimk] + c);
		}
	}
	cout << dp[n][m];
}

3.10输出任意一种合法方案

1013. 机器分配
反向搜索，不用担心找不到，因为是一层一层推的，所以所有点都可以找到方案

#include<bits/stdc++.h>
using namespace std;
int dp[11][16];//给剩下的数量，执行了几个
int a[16][16];
void dfs(int n,int m){
	if(n == 1)
	{
		cout << 1 << ' ' << m << endl;
		return;
	}
	for(int i = 0;i <= m;i++){
		if(dp[n][m] == a[n][i] + dp[n - 1][m-i]){
			dfs(n-1,m-i);
			cout << n << ' ' << i << endl;
			return;
		}
	}
}
int main()
{
	int n,m;cin >> n >> m;
	for(int i = 1;i <= n;i++){
		for(int k = 0;k <= m;k++)
			dp[i][k] = dp[i - 1][k];
		for(int j = 1;j <= m;j++){
			cin >> a[i][j];
			for(int k = j;k <= m;k++)
				dp[i][k] = max(dp[i][k],dp[i - 1][k - j] + a[i][j]);
		}
	}
	cout << dp[n][m] << endl;
	dfs(n,m);
}

3.11有依赖的背包问题

10.有依赖的背包问题
先处理子节点，再处理父节点

#include<bits/stdc++.h>
using namespace std;
vector<int> son[101];
int dad[101];
int n,V,root;
int v[101],w[101];
int dp[2][101][101];
void dfs(int i){
	int op = 0;
	for(int j = v[i];j <= V;j++)
		dp[op][i][j] = dp[1 - op][i][j] = w[i];
	for(auto _i:son[i]){//更新所有子节点
		dfs(_i);
		op = 1 - op;
		for(int j = v[i];j <= V;j++)
			for(int k = 0;j - k >= v[i];k++)
				dp[op][i][j] = max(dp[op][i][j],max(dp[1-op][_i][k],dp[op][_i][k]) + dp[1-op][i][j - k]);
	}
}
int main()
{
	cin >> n >> V;
	for(int i = 1;i <= n;i++){
		cin >> v[i] >> w[i] >> dad[i];
		if(dad[i] == -1){
			root = i;
			continue;
		}
		son[dad[i]].push_back(i);
	}
	dfs(root);
	cout << max(dp[0][root][V],dp[1][root][V]);
}

分组背包就是一组内只能取一种状态，所以我们记录更新前的背包，对这组数据用更新前的背包更新新背包，这样就不会使数据重复更新，一般用滚动数组实现

3.12背包问题求方案数

11. 背包问题求方案数
更新就替换方案数，相同就加上，最后统计时有可能体积不同但是最大值一样

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
const int MAXV = 1e3 + 10;
bool able[MAXV];
pair<ll,ll> dp[MAXV];
int main()
{
	able[0] = 1;
	dp[0].second = 1;
	int n,v;cin >> n >> v;
	for(int i = 1;i <= n;i++){
		int _v,_w;cin >> _v >> _w;
		for(int j = v;j >= _v;j--){
			if(able[j - _v])
			{
				if(dp[j - _v].first + _w > dp[j].first)
				{
					dp[j].first = dp[j - _v].first + _w;
					dp[j].second = dp[j - _v].second;
					able[j] = 1;
				}
				else if(dp[j - _v].first + _w == dp[j].first){
					dp[j].second = (dp[j].second + dp[j - _v].second) % mod;
				}
			}
		}
	}
	ll num = 0;
	ll ma = 0;
	for(int i = v;i >= 0;i--){
		if(able[i]){
			if(dp[i].first > ma){
				ma = dp[i].first;
				num = dp[i].second;
			}
			else if(dp[i].first == ma){
				num = (num + dp[i].second) % mod;
			}
		}
	}
	cout << num << endl;
}

3.13背包问题求具体方案

12. 背包问题求具体方案
要字典树最小的具体方案，那么较小的必须先判断能否取到最大的方案，那么就要让它最后更新背包，标记这个体积下能否用它更新背包，说明可以取

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
int dp[MAXN][MAXN];
int v[MAXN],w[MAXN];
bool able[MAXN][MAXN];
int main()
{
	int n,V;cin >> n >> V;
	for(int i = 1;i <= n;i++)
	{
		cin >> v[i] >> w[i];
	}
	for(int i = n;i >= 1;i--){
		for(int j = 1;j <= V;j++){
			dp[i][j] = dp[i + 1][j];//先不取
			if(j >= v[i] && dp[i][j] <= dp[i + 1][j - v[i]] + w[i])
			{
				able[i][j] = 1;
				dp[i][j] = dp[i + 1][j - v[i]] + w[i];
			}
		}
	}
	int now = V;
	for(int i = 1;i <= n;i++){
		if(able[i][now])//能取
		{
			cout << i << ' ';
			now -= v[i];
		}
	}
}

3.14贪心确定顺序后背包

734. 能量石
假设最优解为\(p_1,p_2,p_3...\)那么无论如何交换最优解的顺序都不能让答案变大，所以我们可以用贪心先确定这个顺序，然后用背包确定哪些取，那些不取

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 101,MAXS = 1e4;
struct rock{
	int s,e,l;
}r[MAXN];
bool cmp(rock a,rock b){
	return a.e + b.e - b.l*a.s > b.e + a.e - b.s*a.l;
}
int dp[MAXS];
int main()
{
	int t;cin >> t;
	int ptop=1;
	while(t--){
		memset(dp,0,sizeof(dp));
		int n;cin >> n;
		for(int i = 1;i <= n;i++){
			cin >> r[i].s >> r[i].e >> r[i].l;
		}
		sort(r + 1,r + 1 + n,cmp);
		int ma = 0;
		for(int i = 1;i <= n;i++){
			for(int j = MAXS - 1;j >= r[i].s;j--){
				dp[j] = max(dp[j],dp[j - r[i].s] + r[i].e - r[i].l*(j - r[i].s));
				ma = max(dp[j],ma);
			}
		}
		cout << "Case #" << ptop << ": " << ma << endl;
		ptop++;
	}
}

4.状态机

将状态转换为特定的数字，根据状态之间的转换来确定
1049. 大盗阿福
设偷这个店的状态为1，不偷为0，就有状态转换：不偷可以由偷和不偷转移，偷只能由不偷转移
\(dp[i][0]=max(dp[i-1][1],dp[i-1][0])\)
\(dp[i][1]=dp[i-1][0]+w\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int dp[MAXN][2];
int main(){
	int t;cin >> t;
	while(t--){
		memset(dp,0,sizeof(dp));
		int n;cin >> n;
		for(int i = 1;i <= n;i++){
			int v;cin >> v;
			dp[i][1] = dp[i - 1][0] + v;
			dp[i][0] = max(dp[i - 1][0],dp[i - 1][1]);
		}
		cout << max(dp[n][0],dp[n][1]) << endl;
	}
}

1057. 股票买卖 IV
假设持有股票为1，没有为0，就有\(dp[第几个][交易了几轮][是否有股票]\)
\(dp[i][j][0]=max(dp[i-1][j-1][1]+v,dp[i-1][j][0])\)
\(dp[i][j][1]=max(dp[i-1][j][0]-v,dp[i-1][j][1])\)
还能用滚动数组优化

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int dp[2][101][2];
int main()
{
	int n,k;cin >> n >> k;
	int op = 0;
	for(int i = 0;i <= 1;i++)
	for(int j = 0;j <= k;j++)
	dp[0][j][i] = dp[1][j][i] = -1e9;
	for(int j = 0;j <= k;j++)
		dp[0][j][0] = dp[0][j][1] = 0;//初始状态
	int ma = 0;
	for(int i = 1;i <= n;i++){
		int v;cin >> v;
		for(int j = k - 1;j >= 0;j--){
			dp[0][j + 1][1 - op] = max(dp[0][j + 1][op],dp[1][j][op] + v);
			ma = max(dp[0][j + 1][1 - op],ma);
			dp[1][j][1 - op] = max(dp[1][j][op],dp[0][j][op] - v);
		}
		op = 1 - op;
	}
	cout << ma << endl;
}

1058. 股票买卖 V
多了一个冷却状态2
\(dp[i][j][2]=dp[i-1][j][1]\)
\(dp[i][j][1]=max(dp[i-1][j-1][0]+w,dp[i-1][j][1])\)
\(dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][2])\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int dp[3][2];//0无,1有,2冷却
int main()
{
	int n,op = 0;cin >> n;
	dp[1][1] = dp[1][0] = dp[2][1] = dp[2][0] = -1e9;//不存在
	for(int i = 1;i <= n;i++){
		int x;cin >> x;
		dp[0][op] = max(dp[2][1 - op],dp[0][1 - op]);
		dp[1][op] = max(dp[0][1 - op] - x,dp[1][1 - op]);
		dp[2][op] = dp[1][1 - op] + x;
		op = 1 - op;
	}
	cout << max(dp[0][1 - op],dp[2][1 - op]);
}

其他

最大k块连续序列之和

A - Max Sum Plus Plus
令\(dp[2][N]\)，第一个参量表示是否取了上一个数，第二个参量表示是否取了多少块，本身代表和

#include<bits/stdc++.h>//
using namespace std;

#define ll long long 
inline int read() {
    int X=0,w=1; int c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
    return X*w;
}
inline void write(ll x)
{
    if(x<0){
    	putchar('-');
		x=-x;
	}
    if(x>9) 
		write(x/10);
    putchar(x%10+'0');
}

const int N = 1e6 + 10,inf = 1e9 + 10;
int dp[N];
int ma[N];
int a[N];

int main(){
	int m,n;
	while(~scanf("%d %d",&m,&n)){
		for(int i = 1;i <= n;i++)
			a[i] = read();
		memset(dp,0,sizeof(dp));dp[0] = -inf;
		memset(ma,0,sizeof(ma));
		int maa;
		for(int i = 1;i <= m;i++){
			maa = -inf;
			for(int j = 1;j <= n;j++){
				dp[j] = max(dp[j - 1] + a[j],ma[j - 1] + a[j]);
				ma[j - 1] = maa;
				maa = max(dp[j],maa);
			}
		}
		printf("%d\n",maa);
	}
}

单调栈求最大可行矩形

二维H - 棋盘制作
一维Largest Rectangle in a Histogram
对于一个大矩形中有一些点不可行，然后要求最大可行矩形问题，用单调栈解决
栈内元素单调递增，如果遇到小的数，说明栈顶的元素无法向右继续延伸了，用现在的位置减去它的左边界就是最大的宽度
同时距离去掉的最左边边界，这就是新元素的左边界了（去掉的都比新元素大）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
ll w[N],a[N];
int main(){
    ios::sync_with_stdio(false);//写了using namespace std;
    ll n;cin >> n;
    while(n){
        stack<pair<ll,ll>> st;
        ll ma = 0;
        for(int i = 1;i <= n;i++){
            ll x;cin >> x;
            ll l = i;
            while(!st.empty() && x < st.top().first){
                ma = max(ma,(i - st.top().second)*st.top().first);
                l = min(st.top().second,l);
                st.pop();
            }
            st.push({x,l});
        }
        while(!st.empty()){
            ma = max(ma,(n + 1 - st.top().second)*st.top().first);
            st.pop();
        }
        cout << ma << endl;
        cin >> n;
    }
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N = 2e3 + 10;
bool mp[N][N];
int dp[2][N][N];
int a[N];
signed main(){
	ios::sync_with_stdio(false);//写了using namespace std;
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	for(int j = 1;j <= m;j++){
		cin >> mp[i][j];
		mp[i][j] ^= ((i + j) % 2);
	}
	int ma1 = 0,ma2 = 0;
	bool f = 1;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(mp[i][j])
				dp[1][i][j] = dp[1][i - 1][j] + 1;
			else
				dp[0][i][j] = dp[0][i - 1][j] + 1;
		}
		stack<pair<int,int>> st;
		for(int j = 1;j <= m;j++){
			int l = j;
			while(!st.empty() && dp[1][i][j] < st.top().first){
				int wid = j - st.top().second;
				int h = st.top().first;
				ma1 = max(min(h,wid)*min(h,wid),ma1);
				ma2 = max(h*wid,ma2);
				l = st.top().second;
				st.pop();
			}
			st.push({dp[1][i][j],l});
		}
		while(!st.empty()){
			int wid = m + 1 - st.top().second;
			int h = st.top().first;
			ma1 = max(min(h,wid)*min(h,wid),ma1);
			ma2 = max(h*wid,ma2);
			st.pop();
		}
		for(int j = 1;j <= m;j++){
			int l = j;
			while(!st.empty() && dp[0][i][j] < st.top().first){
				int wid = j - st.top().second;
				int h = st.top().first;
				ma1 = max(min(h,wid)*min(h,wid),ma1);
				ma2 = max(h*wid,ma2);
				
				l = st.top().second;
				st.pop();
			}
			st.push({dp[0][i][j],l});
		}
		while(!st.empty()){
			int wid = m + 1 - st.top().second;
			int h = st.top().first;
			ma1 = max(min(h,wid)*min(h,wid),ma1);
			ma2 = max(h*wid,ma2);
			st.pop();
		}
	}
	cout << ma1 << endl << ma2 << endl;
}

最长相同子序列

L - Common Subsequence
\(dp[i][j]\)第一个字符串枚举到那里，第二个，记录长度

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

int dp[N][N];

int main()
{
	string s1,s2;
	while(cin >> s1 >> s2){
		int n = s1.size(),m = s2.size();
		memset(dp,0,sizeof(dp));
		s1 = ' ' + s1,s2 = ' ' + s2;
		for(int j = 1;j <= n;j++)
			for(int k = 1;k <= m;k++){
				if(s1[j] == s2[k]){
					dp[j][k] = dp[j - 1][k - 1] + 1;
				}else{
					dp[j][k] = max(dp[j - 1][k],dp[j][k - 1]);
				}
			}
		cout << dp[n][m] << endl;
	}
	
}

centos7 openssh centos p1

p1-hi-a 469 p1 hi

526互联

动态规划 P1

动态规划

1.数字三角形模型

1.1只取一条最大路或最小路

1.2取两条路，可重叠

1.3取两条路，不可重叠

2.最长上升子序列模型

2.1求最长长度

2.2求最长山形

2.3引索型最长子序列

2.4最少递增序列

2.5求最大的上升子序列

2.6最少分割单调子序列

2.7最长公共上升子序列

addtion 2.8最长下降子序列及计不同序列数量

3.背包模型

3.1 01背包问题

3.2二重01背包问题

3.3 01背包状态出现次数

3.4完全背包求方案数

3.5最少的数来组合出所有数

3.6单调队列+滑动窗口+滚动数组优化多重完全背包

3.7简单的混合背包

3.8二维费用背包

3.9满足条件或更好的最值背包

3.10输出任意一种合法方案

3.11有依赖的背包问题

3.12背包问题求方案数

3.13背包问题求具体方案

3.14贪心确定顺序后背包

4.状态机

其他

最大k块连续序列之和

单调栈求最大可行矩形

最长相同子序列

526互联

动态规划 P1

动态规划

1.数字三角形模型

1.1只取一条最大路或最小路

1.2取两条路，可重叠

1.3取两条路，不可重叠

2.最长上升子序列模型

2.1求最长长度

2.2求最长山形

2.3引索型最长子序列

2.4最少递增序列

2.5求最大的上升子序列

2.6最少分割单调子序列

2.7最长公共上升子序列

addtion 2.8最长下降子序列及计不同序列数量

3.背包模型

3.1 01背包问题

3.2二重01背包问题

3.3 01背包状态出现次数

3.4完全背包求方案数

3.5最少的数来组合出所有数

3.6单调队列+滑动窗口+滚动数组 优化多重完全背包

3.7简单的混合背包

3.8二维费用背包

3.9满足条件或更好的最值背包

3.10输出任意一种合法方案

3.11有依赖的背包问题

3.12背包问题求方案数

3.13背包问题求具体方案

3.14贪心确定顺序后背包

4.状态机

其他

最大k块连续序列之和

单调栈求最大可行矩形

最长相同子序列

3.6单调队列+滑动窗口+滚动数组优化多重完全背包