dp(背包dp,区间dp,线性dp)学习笔记

By Jeffery

背包dp(例题:P1776 宝物筛选)

题目传送门

背包dp有很多种,如:01背包,多重背包,完全背包。这里的例题便是经典的多重背包。

第一步:读懂题目(包括对象,已知条件,所求内容)

已知条件:宝物种数,采集车的最大载重,每种宝物的的价值​,每种宝物的重量,每种宝物的件数。

所求内容:采集车不超载的情况下收集的宝物的最大价值。

第二步:分析怎么求(算法分析)

结合本文,算法标签和题目中明显的物品重量,物品个数,物品价值等,我们都可以判断出此题为多重背包dp题目。

方法一(朴素dp,30分)的dp六要素

阶段:前$i$种宝物,采集车的最大载重$j$,前$k$个物品

状态:dp[$i$][$j$]表示处理到前$i$种宝物,采集车的最大载重为$j$时的采集车不超载的情况下收集的宝物的最大价值。

决策:不放此宝物或放1~$k$件宝物

状态转移方程:dp[i][j]=max(dp[i][j]/*不放此宝物*/,dp[i-1][j-k*h[i]]+k*u[i]/*选取k件当前宝物*/)

初始值: dp[0][1]=0

目标值:dp[n][w]

方法二(二进制优化dp,100分)的dp六要素

阶段:前$i$种宝物,采集车的最大载重$j$

状态:dp[$j$]表示处理到采集车的最大载重为$j$时的采集车不超载的情况下收集的宝物的最大价值

决策:不放宝物或放宝物

状态转移方程:dp[j]=max(dp[j],dp[j-w[i]]+v[i])

初始值: dp[0]=0

目标值:dp[wi]

第三步:分析该算法的核心代码

方法一(朴素dp,30分)

for(int i=1;i<=n;++i)//循环前i种宝物
{
	for(int j=1;j<=w;j++)//循环采集车的最大载重
	{
		for(int k=0;k<=m[i]&&k*h[i]<=j;k++)//循环前k个物品
		{
			dp[i][j]=max(dp[i][j]/*不放此宝物*/,dp[i-1][j-k*h[i]]+k*u[i]/*选取k个当前宝物*/);
		}
	}
}

方法二(二进制优化dp,100分)

for(int i=1;i<=cnt;++i)//循环第i个宝物
{
    for(int j=wi;j>=w[i];--j)//循环采集车的最大载重
	{
		dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
	}
}

第四步:代码呈现

方法一(朴素dp,30分)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAX 10000
using namespace std;
int n,w,u[MAX],h[MAX],m[MAX],dp[MAX][MAX];
//n:宝物种数;w:采集车的最大载重;u:每种宝物的价值;h:每种宝物的重量,m:每种宝物件数
int main()
{
	scanf("%d%d",&n,&w);
	for(int i=1;i<=n;++i)scanf("%d%d%d",&u[i],&h[i],&m[i]);
	for(int i=1;i<=n;++i)//循环前i种宝物
	{
		for(int j=1;j<=w;j++)//循环采集车的最大载重
		{
			for(int k=0;k<=m[i]&&k*h[i]<=j;k++)//循环前k个物品
			{
				dp[i][j]=max(dp[i][j]/*不放此宝物*/,dp[i-1][j-k*h[i]]+k*u[i]/*选取k个当前宝物*/);
			}
		}
	}
	printf("%d",dp[n][w]);
    return 0;
}

方法二(二进制优化dp,100分)

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX 100001
using namespace std;
int n,wi,v[MAX],w[MAX],dp[MAX],a,b,c,cnt=0;
//n:宝物种数;wi:采集车的最大载重;v:每种宝物的价值;w:每种宝物的重量
//dp[i]:采集车的最大载重为i时的收集的宝物的最大价值
//a,b,c:价值为a,重量为b,每种宝物有c件;cnt:宝物总个数(不是种数)
int main()
{
	scanf("%d%d",&n,&wi);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d%d",&a,&b,&c);
		for(int j=1;j<=c;++j)
		{
			cnt++;
			v[cnt]=j*a;
			w[cnt]=j*b;
			c-=j;
		}
		if(c)
		{
			cnt++;
			v[cnt]=a*c;
			w[cnt]=b*c;
		}
	}
	for(int i=1;i<=cnt;++i)//循环第i个宝物
	{
		for(int j=wi;j>=w[i];--j)//循环采集车的最大载重
		{
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	printf("%d",dp[wi]);
    return 0;
}

区间dp(例题:P1775 石子合并（弱化版）)

题目传送门

第一步：读懂题目(包括对象，已知条件，所求内容)

已知:$n$堆石子的重量

所求:合并石子最小代价

第二步:分析:怎么求，用什么算法求解(算法 分析)

结合算法标签和题目中明显的"$N$堆",我们都可以判断出此题为区间dp题目。
阶段 $i$开始,长为$len$的区间

状态 dp[$i$][$j$]表示处理到$i$~$j$区间时的合并最小代价

决策 合并或不合并

状态转移方程 dp[i][j]/*状态*/=min(dp[i][j]/*不合并*/,dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]/*合并*/)

初始值

memset(dp,63,sizeof(dp));//初始化为INF
for(int i=1;i<=n;i++)
{
	dp[i][i]=0;//初始化dp数组的另一部分(i~i的最优解)
}

目标值 dp[i][n]

第三步：分析该算法的核心代码

for(int len=2;len<=n;++len)//阶段:枚举长度
{
	for(int i=1;i+len-1<=n;i++)//状态:枚举起点[i]
	{
		int j=i+len-1;//状态:计算终点[j]
		for(int k=i;k<j;k++)
		{
			dp[i][j]/*状态*/=min(dp[i][j]/*不合并*/,dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]/*合并*/);//状态转移方程
		}
	}
}

第四步：代码呈现

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX 301
using namespace std;
int n,dp[MAX][MAX],sum[MAX];
int main()
{
	memset(dp,63,sizeof(dp));//初始化为INF
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		dp[i][i]=0;//顺便初始化dp数组的另一部分(i~i的最优解)
		int tmp;
		scanf("%d",&tmp);
		sum[i]=sum[i-1]+tmp;//前i堆石子的重量总和
	}
	for(int len=2;len<=n;++len)//阶段:枚举长度
	{
		for(int i=1;i+len-1<=n;i++)//状态:枚举起点[i]
		{
			int j=i+len-1;//状态:计算终点[j]
			for(int k=i;k<j;k++)
			{
				dp[i][j]/*状态*/=min(dp[i][j]/*不合并*/,dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]/*合并*/);//状态转移方程
			}
		}
	}
	printf("%d",dp[1][n]);
    return 0;
}

线性dp(例题:T355255 LIS)

题目传送门

第一步：读懂题目(包括对象，已知条件，所求内容)

已知:一个长度为n的队列

所求:${\color{Red}最长上升子序列}$的${\color{Red}长度}$(可间断)

第二步:分析:怎么求，用什么算法求解(算法分析)

由于本题为最长上升子序列(lis)的模板题，所以我们显而易见地知道本题应该使用线性dp。

线性dp是在线性结构上进行状态转移,它除了在最本题(最长上升子序)列及其类似问题(如:最长不上升子序列等)之外,一般没有固定模板。

本题的dp六要素(50分):

阶段 $j$开始到$i$的子序列(不一定连续)

状态 dp[$i$]表示处理到前$i$个数时的子序列的长度

决策 选择接上或不接上处理到前$j$个数时的子序列
例:
在3-6-4-2-5-8-5中在i=5,j=3时
便可使用 3-4接上当前的5-8
形成 3-4-5-8

状态转移方程 dp[i]=max(dp[i],dp[j]+1);

初始值 dp[i]=1 ($1$<=$i$<=$n$)

目标值 max{dp[i]} ($1$<=$i$<=$n$)

本题的dp六要素(100分,lower_bound优化):

阶段 第1,2,3,4……$n$个数(以第$i$个数为结尾)

状态 dp[$i$] ${\color{Purple}上升子序列 长度为i}$,${\color{Red}状态数组存储的是}$序列结尾的最小值

决策 用到了第i个元素,和它在1到$i$间的元素,${\color{red}决策组}$组成有的一个状态

状态转移方程

if(dp[ans]<a[i])
{
	ans++;
	dp[ans]=a[i];
}
else
{
	*(lower_bound(dp+1,dp+1+ans,a[i]))=a[i];//使用lower_bound进行查找
}

初始值 dp[1]=a[1]

目标值 ans

第三步：分析该算法的核心代码

50分

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

100分,lower_bound优化

for(int i=2;i<=n;++i)
{
	if(dp[ans]<a[i])
	{
		ans++;
		dp[ans]=a[i];
	}
	else
	{
		*(lower_bound(dp+1,dp+1+ans,a[i]))=a[i];//使用lower_bound进行查找
	}
}

第四步：代码呈现

50分

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAX 200001
using namespace std;
int n,a[MAX],dp[MAX];//dp[i]表示第i个数结尾的子序列
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		dp[i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<i;++j)
		{
			if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+1);
		}
	}
	int ans=1;
	for(int i=1;i<=n;i++)if(dp[i]>ans)ans=dp[i];
	printf("%d",ans);
    return 0;
}

100分,lower_bound优化

#include <iostream>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>
#define MAX 200001
using namespace std;
int n,ans=1,a[MAX],dp[MAX];//dp[i]表示长度为i的上升子序列的末尾的数字
int main()
{

	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
	}
	dp[1]=a[1];
	for(int i=2;i<=n;++i)
	{
		if(dp[ans]<a[i])
		{
			ans++;
			dp[ans]=a[i];
		}
		else
		{
			*(lower_bound(dp+1,dp+1+ans,a[i]))=a[i];//使用lower_bound进行查找
		}
	}
	printf("%d",ans);
	return 0;
}