首页 > 其他分享 >DP

DP

时间：2024-09-10 18:48:12浏览次数：1  
标签：include int max DP now 1010 dp

动态规划

  • 动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

三个条件：最优子结构，无后效性和子问题重叠。

最优子结构

  • 证明问题最优解的第一个组成部分是做出一个选择；
  • 对于一个给定问题，在其可能的第一步选择中，假定你已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择；
  • 是否可以选择到当前最优

无后效性

  • 当前的最优子问题，不会再受到后续决策的影响。

子问题重叠

  • 可以通过储存答案的方式来避免重复求解相同的子问题，从而提升效率。；

基本方案

  • 将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为状态）；
  • 寻找每一个状态的可能决策，或者说是各状态间的相互转移方式（用数学的语言描述就是状态转移方程）。
  • 按顺序求解每一个阶段的问题。

背包DP

01背包

通常问题为给你可以使用的最大容积m，所有物品n的价值w[i]和体积v[i]，求最大价值

二维
  • 定义状态 dp[i][j]表示前i个物品使用了j的体积可以获得的最大价值
  • 状态转移 dp[i][j]=max(dp[iz][j],dp[i-1][j-v[i]]+w[i]);
  • 输出结果 dp[n][m]
#include<bits/stdc++.h>
using namespace std;
int w[1010],dp[1010][1010],sum[1010];
int m,t;
int main(){
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>sum[i]>>w[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=t;j++){
			dp[i][j]=max(dp[i-1][j],dp[i][j]);
			if(j>=sum[i]){
				dp[i][j]=max(dp[i][j],dp[i-1][j-sum[i]]+w[i]);
			}
		}
	}
	cout<<dp[m][t];
	return 0;
}
一维
  • 定义状态 dp[j]表示使用体积为j的背包获得的最大价值
  • 状态转移 dp[j]=dp[j-v[i]]+w[i]
  • 输出结果 dp[m]
#include<bits/stdc++.h>
using namespace std;
int t,m;
int v[210],w[210];
int dp[2100];
signed main(){
	ios::sync_with_stdio(false);
	cin>>t>>m;
	for(int i=1;i<=m;i++)	cin>>v[i]>>w[i];
	for(int i=1;i<=m;i++){
		for(int j=t;j>=v[i];j--){
			dp[j]=max(dp[j-v[i]]+w[i],dp[j]); 
		}
	}
	cout<<dp[t];
	return 0;
}

注意：一维循环容积需要倒过来，这样才能保证只用了一次，其没有破坏上一次的更新

完全背包

与01背包类似，但没有每种物品只能使用一次的要求

二维
  • 定义状态 dp[i][j]表示前i个物品使用了j的体积可以获得的最大价值
  • 状态转移 dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
  • 输出结果 dp[n][m]
#include<bits/stdc++.h>
using namespace std;
int w[1010],dp[1010][1010],sum[1010];
int m,t;
int main(){
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>sum[i]>>w[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=t;j++){
			dp[i][j]=max(dp[i-1][j],dp[i][j]);
			if(j>=sum[i]){
				dp[i][j]=max(dp[i][j],dp[i][j-sum[i]]+w[i]);
			}
		}
	}
	cout<<dp[m][t];
	return 0;
}
一维
  • 定义状态 dp[j]表示使用了j的体积可以获得的最大价值
  • 状态转移 dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
  • 输出结果 dp[m]
#include<bits/stdc++.h>
using namespace std;
int w[1010],dp[1010],sum[1010];
int m,t;
int main(){
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>sum[i]>>w[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=sum[i];j<=t;j++){
			dp[j]=max(dp[j],dp[j-sum[i]]+w[i]);
		}
	}
	cout<<dp[t];
	return 0;
}

注意：枚举时要正着，想想为什么

多重背包

与01背包类似，但加上了最多一个可以装k[i]次

二维
  • 定义状态 dp[i][j]表示前i个物品使用了j的体积可以获得的最大价值
  • 状态转移 dp[i][j]=max(dp[i][j],dp[i-1][j-cv[i]]+cw[i]);
  • 输出结果 dp[n][m]
#include<bits/stdc++.h>
using namespace std;
int k[2010];
int w[1010],dp[1010][1010],sum[1010];
int m,t;
int main(){
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>sum[i]>>w[i]>>k[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=t;j++){
			for(int c=0;c<=k[i]&&c*v[i]<=j;c++){
				dp[i][j]=max(dp[i][j],dp[i-1][j-c*sum[i]]+c*w[i]);	
			}
		}
	}
	cout<<dp[m][t];
	return 0;
}
一维
  • 定义状态 dp[j]表示使用了j的体积可以获得的最大价值
  • 状态转移 dp[j]=max(dp[j],dp[j-v[i]c]+w[i]c);
  • 输出结果 dp[m]
#include<bits/stdc++.h>
using namespace std;
int t,m;
int v[210],w[210];
int dp[2100];
int k[1010];
signed main(){
	ios::sync_with_stdio(false);
	cin>>t>>m;
	for(int i=1;i<=m;i++)	cin>>v[i]>>w[i]>>k[i];
	for(int i=1;i<=m;i++){
		for(int j=t;j>=v[i];j--){
			for(int c=0;c<=k[i]&&c*v[i]<=j;c++)
				dp[j]=max(dp[j-v[i]*c]+w[i]*c,dp[j]); 
		}
	}
	cout<<dp[t];
	return 0;
}

分组背包

与01背包类似

只需要加上k组中每组选一个最大的即可

#include<bits/stdc++.h>
using namespace std;
int n,m,maxn;
int a[10010],b[10001],dp[1100],c,t[1010],ans[1010][1100];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c;
		maxn=max(maxn,c);
		ans[c][++t[c]]=i;
	}
	for(int i=1;i<=maxn;i++){
		for(int j=m;j>=0;j--){
			for(int k=1;k<=t[i];k++){
				if(j>=a[ans[i][k]]){
					dp[j]=max(dp[j],dp[j-a[ans[i][k]]]+b[ans[i][k]]);
				}
			}
		}
	}
	cout<<dp[m];
	return 0;
}

LIS与LCS

最长上升子序列(LIS)

  • 给出一个序列，求最长上升子序列
    -设dp[i]表示前i个数的最长上升子序列是多长
    -dp[i]=max((dp[j]+1)*(a[j]<a[i]),dp[i])(j<i)
#include<bits/stdc++.h>
using namespace std;
long long n,a[5010],dp[5010];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i];
	dp[1]=1;
	for(int i=2;i<=n;i++){
		dp[i]=1;
		for(int j=1;j<=i-1;j++){
			dp[i]=max(dp[i],(dp[j]+1)*(a[j]<a[i]));
		}
	}
	long long maxn=-1e9;
	for(int i=1;i<=n;i++)
		maxn=max(maxn,dp[i]); 
	cout<<maxn;
	return 0;
}

但此方法只能通过O(N*N)的数据，我们还可以进行优化。

  • 通过维护一个单调递增的队列，来求最长上升子序列。
  • 期间通过二分的方法，来找到当前的值可以放在队列中的最优位置。
  • 最后答案就是队列的大小
#include<bits/stdc++.h>
using namespace std;
int n,a[20010];
int dp[20010];
int main(){
	cin>>n;
	int len=0;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1;i<=n;i++){
		if(a[i]>=dp[len]){
			dp[++len]=a[i];continue;
		}
		int tot=lower_bound(dp+1,dp+1+len,a[i])-dp;
		dp[tot]=a[i];
	}
	cout<<len; 
	return 0;
}

最长公共子序列(LCS)

  • 给出两个序列，求最长公共子序列
    -设dp[i][j]表示第一个序列前i个数与第二个序列的前j个匹配的最长公共子序列是多长
  • if(s1[i]==s2[j]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
    -如果不满足那就继承上一次更新的。
  • if(s1[i]!=s2[j]) dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
#include<bits/stdc++.h>
using namespace std;
int n;
int dp[5010][5010];
string s1,s2;
int main(){
	cin>>n;
	s1=" "+s1;
	int len1=s1.size()-1;
	s2=" "+s2;
	int len2=s2.size()-1;
	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][j],dp[i-1][j-1]+1);
			}
			else{
				dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
			}
		}
	}	
	cout<<dp[len1][len2];
	return 0;
}

区间DP

  • 顾名思义，区间DP，是把小区间转移到大区间，从而解决全局性问题。

一般有以下特点

  • 合并：将两个或多个部分进行整合，当然也可以反过来；
    -特征：能将问题分解为能两两合并的形式；
    -求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

例题：

石子合并

  • 给定一排石子，合并代价为两堆的代价和，求一堆时最小代价
  • 设dp[l][r]表示l~r区间的最小代价；
  • dp[l][r]=dp[l][k]+dp[k+1][r]+pre[r]-pre[l-1]
  • 一个区间可以由两个区间的各自价值加上两堆本身的价值
#include<bits/stdc++.h>
using namespace std;
int n;
int dp[110][110];
int pre[110];
int a[110];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)	dp[i][j]=INT_MAX;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pre[i]=pre[i-1]+a[i];
		dp[i][i]=0;
	}
	for(int len=2;len<=n;len++){
		for(int l=1;l<=n-len+1;l++){
			int r=l+len-1; 	
			for(int k=l;k<r;k++){
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+pre[r]-pre[l-1]);
			}
		}
	} 
	cout<<dp[1][n];
	return 0;
}

关路灯

  • 初始站在一个位置，给定每一个路灯的位置与每一秒的耗能，求怎样关路灯使耗能最少。
  • 由题意得每一个区间要最后到一个地方最优，这个位置一定是最左或最右边。
  • 所以设dp[l][r][0/1]为把区间l~r的区间全部关完站在（左/右）端点的最小值
  • 转移为 当前节点从一旁区间的（左/右）端点走到当前端点所有没有关的路灯的总耗能，可以用前缀和维护。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c;
int a[210],dp[110][110][2];
int pre[210];
int d;
signed main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>d;
		pre[i]=pre[i-1]+d;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j][0]=dp[i][j][1]=INT_MAX;
		}
	}
	dp[c][c][0]=dp[c][c][1]=0;
	for(int i=1;i<=n;i++){
		if(i!=c){
			dp[i][i][0]=dp[i][i][1]=abs(a[c]-a[i])*pre[n];
		}		
	}
	for(int len=2;len<=n;len++){
		for(int l=1;l<=n-len+1;l++){
			int r=l+len-1;
			dp[l][r][0]=min(dp[l][r][0],dp[l+1][r][0]+(a[l+1]-a[l])*(pre[n]-(pre[r]-pre[l])));
			dp[l][r][0]=min(dp[l][r][0],dp[l+1][r][1]+(a[r]-a[l])*(pre[n]-(pre[r]-pre[l])));
			dp[l][r][1]=min(dp[l][r][1],dp[l][r-1][0]+(a[r]-a[l])*(pre[n]-(pre[r-1]-pre[l-1])));
			dp[l][r][1]=min(dp[l][r][1],dp[l][r-1][1]+(a[r]-a[r-1])*(pre[n]-(pre[r-1]-pre[l-1])));
		}
	}
	cout<<min(dp[1][n][1],dp[1][n][0]);
	return 0;
}

树形DP与树上背包问题

树是什么？

  • n个点n-1条边且没有重边的图，两点之间的简单路径只有一条。

树的重心

  • 定义：以一个点作为根，使其子树的大小最小。

  • 设dp[i]为以i为根的最大字数大小,siz[i]表示子树大小

  • 由定义得：dp[u]=max(dp[u],siz[son[u]]);

  • 最后不要忘了dp[u]=max(dp[u],n-siz[u]);

void dfs(int now,int fa){
    siz[now]=1;
    dp[now]=0;
	for(int i=head[now];i;i=a[i].nxt){
		int to=a[i].to;
		if(to==fa)	continue;
		dfs(to,now);
        siz[now]+=siz[to];
		dp[now]=max(dp[now],siz[to]);	
		
	}	
	dp[now]=max(dp[now],n-siz[now]);
}

树的直径

  • 定义：树的最长两点的距离
  • 设dp[i][0/1]表示以i为父亲节点的[最大/次大]（一点到父亲节点的长度）。
  • 为什么要这样设计？
  • 因为直径就是子树中的最远两点的距离，所以记录两个不同子树的最大值再+1，及从儿子节点跳到父亲节点。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,u,v;
struct node{
	int to,nxt;
}a[200010];
int head[200010],tot;
void add(int x,int y){
	a[++tot].to=y;
	a[tot].nxt=head[x];
	head[x]=tot;
}
int dp[100010][2];
int maxn;
void dfs(int now,int fa){
	for(int i=head[now];i;i=a[i].nxt){
		int to=a[i].to;
		if(to==fa)	continue;
		dfs(to,now);
		if(dp[now][0]<=dp[to][0]+1){
			dp[now][1]=dp[now][0];
			dp[now][0]=dp[to][0]+1;	
		}
		else{
			if(dp[now][1]<=dp[to][0]+1){
				dp[now][1]=dp[to][0]+1;
			}
		}
	}
	maxn=max(maxn,dp[now][0]+dp[now][1]);
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		add(u,v),add(v,u);
	}
	dfs(1,0);
	cout<<maxn;
	return 0;
}

树形DP

  • 从儿子到父亲（子信息合并）
  • 从父亲到儿子（深度累加，答案累加）

例题：

标签：include,int,max,DP,now,1010,dp
From： https://www.cnblogs.com/lmy333/p/18406936

相关文章

  • [DPDK] dumpcap报错EAL init failed: is primary process running?解决办法
    [DPDK]dumpcap报错EALinitfailed:isprimaryprocessrunning?解决办法问题我写了一个DPDK程序，现在想要用DPDK自带的dpdk-dumpcap工具来抓包测试。根据官网描述，我们需要先启动我们的程序为主进程，然后启动dpdk-dumpcap为副进程。但是我直接运行dpdk-dumpcap，显示如下错误：注：......
  • TCP和UDP对比
    TCP和UDP对比TCP（TransmissionControlProtocol，传输控制协议）和UDP（UserDatagramProtocol，用户数据报协议）是两种常用的网络传输层协议，它们在网络通信中扮演着重要的角色。以下是它们的主要区别：连接性：TCP：TCP是一种面向连接的协议，在数据传输之前需要建立一个连接（三次握手），数据......
  • TCP和UDP
    TCP（TransmissionControlProtocol，传输控制协议）和UDP（UserDatagramProtocol，用户数据报协议）是两种常用的网络传输层协议，它们在网络通信中扮演着重要的角色。以下是它们的主要区别：连接性：TCP：是一种面向连接的协议。在数据传输开始之前，必须建立一个连接，通过三次握手过程来确保......
  • NPDP和PMP有啥区别？其实就这个3点
    1、发证机构不同PMP是由项目管理协会PMI发起，严格评估项目管理人员知识技能是否具有高品质的资格认证考试。1999年，中国国际人才交流基金会将项目管理协会制定的《项目管理知识体系指南》和“项目管理专业人士职业资格认证”引入中国。NPDP是由美国产品开发与管理协会PDMA......
  • WPF DataGridTemplateColumn.CellTemplate Command CommandParameter
    <DataGridTemplateColumnHeader="Image"><DataGridTemplateColumn.CellTemplate><DataTemplate><ButtonCommand="{BindingDataContext.EnterCmd,RelativeSource={RelativeSourceFindAn......
  • 【题解】Solution Set - NOIP2024集训Day25 概率期望 dp
    【题解】SolutionSet-NOIP2024集训Day25概率期望dphttps://www.becoder.com.cn/contest/5515「QOJ2606」Gachapon\(f_{i,j}\)：用一次合法的level-irolling能够抽到的\(j\)的期望个数。\(h_{i,j,k}\)：在\(i\)次操作之内，抽到恰好\(k\)个\(j\)的概率。\[h_{i,j,k......
  • 海外合规|新加坡 【数据保护新风向】你的DPO注册了吗？
    数据安全已经成为了我们不可忽视的重要议题。新加坡个人数据保护委员会（PDPC）提醒，2024年9月30日之前，根据新加坡的个人资料保护法（PDPA），每个组织都必须指定至少一名数据保护官（DPO）来确保数据的合规使用。DPO注册相关问题：1、是否必须通过BizFile+注册我组织的DPO？根据法律规定，组织必须......
  • 三格电子——Profibus-DP 转光纤点对点式光端机
    型号：MS-F155-P（Y)一、功能概述MS-F155-P(Y)是将Profibus-DP总线转为光纤的模块，可以延长Profibus通信距离，最远可以达到20公里到40公里。采用光信号传输，模块有很好的抗电磁干扰能力。专用的光纤通信芯片设计电路，使数据通信稳定可靠，可用于比较......
  • 【算法笔记】三种背包问题——背包 DP
    前言背包（Knapsack）问题是经典的动态规划问题，也很有实际价值。01背包洛谷P2871[USACO07DEC]CharmBraceletSAtCoderEducationalDPContestD-Knapsack1有\(n\)个物品和一个总容量为\(W\)的背包。第\(i\)件物品的重量是\(w_i\)，价值是\(v_i\)。求解将哪些物品装入背包......
  • wordpress新增文章新增评论自动通知到微信
    研究了下，如何让wordpress新增文章或者新增评论的时候通知到微信。复制下方代码，粘贴到主题的functions.php文件中即可在wordpress6.6.1版本测试通过理论上支持5.0以上的wp，有问题可以留言反馈/*在pushhub个人中心复制你的token,填入下方获取token:https://www.pushhub.c......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99