首页 > 其他分享 >五大基础dp

五大基础dp

时间:2024-02-17 15:33:05浏览次数:29  
标签:int 基础 hszxoj https tg 五大 com dp

动规条件
最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,
即满足最优化原理。
无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后
的过程不会影响以前的状态,只与当前状态有关。
有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。
(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法
相比就不具备优势)

背包dp

  • 01背包 (一件物品只能选一次)

https://tg.hszxoj.com/contest/897/problem/1

点击查看代码
for(int i=1; i<=n; i++){//外层循环物品
  for(int j=V; j>=v[i]; j--){//内层循环体积 倒叙循环
      dp[j] = max(dp[j], dp[j-v[i]] + w[i];
  }
}
  • 完全背包 (不限制物品数量)

https://tg.hszxoj.com/contest/897/problem/4

点击查看代码
for(int i=1; i<=n; i++){//外层循环物品
  for(int j=v[i]; j<=V; j++){//内层循环体积 顺叙循环
     dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
  }
}

//二进制拆分
for(int i=1; i<=n; i++){
  for(int k=1; k<=V/v[i]; k<<=1){
     for(int j=V; j>=k*v[i]; j--){
       dp[j] = max(dp[j], dp[j-k*v[i]] + k*w[i]);
    }
  }
}
  • 多重背包 (给定物品数量)

https://tg.hszxoj.com/contest/897/problem/6

点击查看代码
//与完全背包一样使用二进制拆分
if(si > m / vi) si = m / vi;
		for(int j=1; j<=si; j<<=1){
			v[++cnt] = j * vi;
			w[cnt] = j * wi;
			si -= j;
		}
		if(si){
			v[++cnt] = si * vi;
			w[cnt] = si * wi;
		}
	}
n = cnt;
  • 混合背包

https://tg.hszxoj.com/contest/897/problem/11
将背包都使用二进制拆分转成01包计算

  • 分组背包

https://tg.hszxoj.com/contest/897/problem/13

点击查看代码
a[p][++a[p][0]] = i;//a[p][0]是每组个数 
for(int p=1; p<=t; p++){
	for(int j=v; j>=w[a[p][i]]; j--){
		for(int i=1; i<=a[p][0]; i++){
			f[j] = max(f[j], f[j-w[a[p][i]]] + c[a[p][i]]);
		}
	}
}

线性dp
顾名思义,线性DP就是在一条线上进行DP
例如:
最长上升序列
https://tg.hszxoj.com/contest/900/problem/1

点击查看代码
for(int i=1; i<=n; i++){
	dp[i] = 1;
	for(int j=1; j<i; j++){
		if(a[i] > a[j] and dp[i] < dp[j] + 1){
			dp[i] = dp[j] + 1;
			pre[i] = j;//记录前一位,方便输出
		}
	}
	if(ans < dp[i]){
		ans = dp[i];
		en = i;//记录结点
	}
}
//递归输出
void p(int x){
	if(!x) return;
	p(pre[x]);
	cout << a[x] << ' ';
}
//由结点开始递归即可
拦截导弹

https://tg.hszxoj.com/contest/900/problem/3

点击查看代码
for(int i=1; i<=n; i++){
	f[i] = 1;
	for(int j=1; j<i; j++){
		if(a[i] <= a[j]){
			f[i] = max(f[i], f[j] + 1);
		}
	}
	ans = max(ans, f[i]);
}

区间dp

这里实际上是以区间长度为阶段的,这种DP我们通常称为区间DP。
区间DP的做法较为固定,即枚举区间长度,再枚举左端点,之后枚举区间的断点进行转移。

区间类型动态规划是线性动态规划的拓展,它在分阶段划分问题时,与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。(例:f[i][j]=f[i][k]+f[k+1][j])

区间类动态规划的特点:

  • 合并:即将两个或多个部分进行整合。
  • 特征:能将问题分解成为两两合并的形式。
  • 求解:对整个问题设最优值,枚举合并点,将问题分解成为左右两个部分,最后将左右两个部分的最优值进行合并得到原问题的最优值。

石子合并<3>
https://tg.hszxoj.com/contest/903/problem/3

点击查看代码
for(int i=1; i<=n*2; i++){//环状就弄成二倍串
		s[i] = s[i-1] + a[i];//求前缀和
	}
	
for(int l=2; l<=n; l++){
	for(int i=1; i+l-1<=n*2; i++){
		int j = i + l - 1;
		g[i][j] = max(g[i+1][j], g[i][j-1]) + s[j] - s[i-1];
	}
}

坐标dp
坐标型dp一般都是给定网格、序列,来求满足某种性质的最大值、最小值。f[i][j]代表以i、j结尾的满足条件的某种情况。

晴天小猪历险记之Hill
https://tg.hszxoj.com/contest/906/problem/5

点击查看代码
dp[1][1] = s[1][1];
for(int i=2; i<=n; i++){
	for(int j=1; j<=i; j++){//从上到下遍历
		dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + s[i][j];
		dp[i][1] = min(dp[i-1][1], dp[i-1][i-1]) + s[i][1];
		dp[i][i] = min(dp[i-1][i-1], dp[i-1][1]) + s[i][i];
	}
		
	for(int j=i-1; j>=1; j--){//从右到左遍历
		dp[i][j] = min(dp[i][j], dp[i][j+1] + s[i][j]);
		dp[i][i] = min(dp[i][i], dp[i][1] + s[i][i]);
	}
		
	for(int j=2; j<=i; j++){//从左到右遍历
		dp[i][j] = min(dp[i][j], dp[i][j-1] + s[i][j]);
		dp[i][1] = min(dp[i][1], dp[i][i] + s[i][1]);
	}
}

树形dp
树形DP的特殊性:没有环,dfs是不会重复,而且具有明显而又严格的层数关系。利用这一特性,我们可以很清晰地根据题目写出一个在树(型结构)上的搜索的程序。而深搜的特点,就是“不撞南墙不回头”

没有上司的舞会
https://tg.hszxoj.com/contest/909/problem/1

使用链表加边,随后dfs进行搜索
dp[x][0] 表示自己不参加 dp[x][1] 表示自己参加

点击查看代码
void dfs(int x){
	for(int i=h[x]; i; i=nxt[i]){
		int y = to[i];
		dfs(y);
		
		dp[x][0] += max(dp[y][1], dp[y][0]);//直接上司不参加, 则下属是否参加取较大值
		dp[x][1] += dp[y][0];//直接上司参加,则下属一定不参加
	}
}
初始化时注意参加即为自己的快乐值,不参加则为0 搜索时从根节点开始搜

标签:int,基础,hszxoj,https,tg,五大,com,dp
From: https://www.cnblogs.com/w12100212/p/18018035

相关文章

  • 背包dp
    01背包:所谓01背包,就是每种物体有一个价值且数量只有一个,给定一个背包容量,在不超出背包容量的前提下在n个物体中取m个,求最大价值。点击查看代码//f[i]指体积为i时的最大价值for(inti=1;i<=n;i++){//第一层循环是指遍历每种物体,n是物体种数 for(intj=m;j>=v[i];j--){//第......
  • 背包DP
    下面介绍一下背包DP主要题型基础模型(没什么好说的,上模板)1.01背包最主要的模板,应用很多,很重要!!!倒着遍历容积,不会受后选小的f[i][j]影响,已经选过的物品不会再选一遍。点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=10020;intf[N];intn,m;intv......
  • 关于动态规划(Dynamic Programming)的若干思考 ------ [1.背包dp]
    背包dp;1.01背包(1)领域展开#include<bits/stdc++.h>//simpleusingnamespacestd;constintmaxm=2024;intn,m;intw[maxm],v[maxm],f[maxm][maxm];intmain(){ cin>>n>>m; for(inti=1;i<=n;i++) cin>>v[i]>>w[i]; for(i......
  • 背包dp
    1、01背包f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i])二维为背包现有容量,一维为前i个物品表示在前i个物品所能选取的最大价值在判断第i个的最大值时要由前一个的状态转移过来;即下一层的状态由上一层转移来;可以直接省掉第一维(压维),从后往前更新过来,若还是正序就会出现一种情况......
  • 【Vue前端】vue使用笔记0基础到高手第2篇:Vue进阶知识点介绍(附代码,已分享)
    本系列文章md笔记(已分享)主要讨论vue相关知识。Vue.js是前端三大新框架:Angular.js、React.js、Vue.js之一,Vue.js目前的使用和关注程度在三大框架中稍微胜出,并且它的热度还在递增。Vue.js是一个轻巧、高性能、可组件化的MVVM库,同时拥有非常容易上手的API。Vue.js是一个构建数据驱动......
  • dp的优化(单队,斜率)
    1.单调队列优化\(dp\)维护最小值:\(x\leqslantq.tail()\)维护最大值:\(x\geqslantq.tail()\)其实原理不难,当\(dp\)的转移源头是一个区间时,往往使用单调队列来维护区间最值(一般队列里装下标以方便维护区间大小,但也只是一般情况),节省了处理区间的时间(甚至噶掉一维),重点是对区间的......
  • 树状DP心得
    说一下近日所学的主要两种题型,一个是分叉情况问题,一种是树上背包问题。分叉情况问题具体的题可以参考小胖守皇宫和三色二叉树。点击查看代码小胖守皇宫#include<bits/stdc++.h>usingnamespacestd;constintN=2000;vector<int>son[N];intfa[N],h[N],f[N][3];//f[0]......
  • vue基础知识和原理(二)
    1.13列表渲染v-for指令用于展示列表数据语法:v-for="(item,index)inxxx":key="yyy"可遍历:数组、对象、字符串(用的很少)、指定次数(用的很少)<divid="root"><!--v-for指令:1.用于展示列表数据......
  • 【网络基础】个人域名申请过程
    1  前言之前趁腾讯云搞活动,买了两台一年的轻量级应用服务器,搭搭自己的微服务,方便自己测试研究嘛,后来看见域名有便宜的,就买了一个,然后要各种备案啊,走流程啊,这里来记录下一个个人域名到能解析到自己的网站的过程哈。我的资源都在腾讯云哈,两台轻量级应用服务器、域名也都是在腾讯......
  • DPInst64.exe difxapi64.dll 是什么 为什么
    DPInst64.exe:安装和卸载驱动程序包。默认情况下,该工具将搜索当前目录,并尝试安装找到的所有驱动程序包。用法:C:\Users\Administrator\Desktop\dp\dp\DPInst64.exe[/UINF文件][/S|/Q][/LM][/P][/F][/SH][/SA][/A][/PATH路径][/EL][/L语言ID][/C][/D][/LogTitle标题][/SW][/?......