首页 > 其他分享 >DP学习笔记

DP学习笔记

时间:2024-08-18 14:15:51浏览次数:11  
标签:int 笔记 学习 tail edge DP 转移 dp 式子

动态规划算法与分治法类似,是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。


动态规划做题思路:

  • 考虑\(dp\)数组每一维状态表示什么

  • 初始化,如果要取\(min\),\(dp\)数组要赋较大的值。\(dp[0]\)的值也要考虑

  • 想转移顺序,逆序or正序。具体想\(i,j\)的范围

  • 想状态转移方程(重点)

  • 想最终结果,一般都表示为\(dp[n][m]\)之类的。。。

PS.由于作者做题经验不足且很懒,有些地方直接就放其他大佬(orz)的博客了,请见谅。

1.线性dp

定义:线性\(DP\)是动态规划问题中的一类问题,指状态之间有线性关系的动态规划问题。(来自百度)这些都是没用的不要看

线性\(dp\)有很多划分方式。一维线性\(dp\)中,\(dp[i]\)一般表示为以\(i\)结尾的最优方案,状态转移方程基本为$$ dp[i]=\max(dp[i], dp[j]+1)$$

最终结果为\(dp[n]\)。

其实也就是for for if。。。

例1:最长上升子序列(划重点)



  
#include<bits/stdc++.h>
using namespace std;
int n, a[50005], f[50005], ans, x, t;
int main()
{
	cin>>n;
	while(cin>>x)
	{	
		t++;
		a[t]=x;	
		if(cin.get()=='\n')
		{
			break;
		}	
	}
	f[1]=1;
	for(int i=2;i<=n;i++)
	{
		f[i]=1;
		for(int j=1;j<i;j++)
		{
			if(a[i]>a[j]&&f[i]<f[j]+1)
			{
				f[i]=f[j]+1;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans=max(ans, f[i]);	
	}
	cout<<ans;
	return 0;
}

比较好理解。

例2:合唱队形

思路:先来一遍最长上升子序列,再来一遍最长不上升子序列,最后枚举求值(题解

#include<bits/stdc++.h>
using namespace std;
int ans, n, a[500005], dp1[500005], dp2[500005];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		dp1[i]=1;
		dp2[i]=1;
	}
	for(int i=n-1;i>=1;i--)
	{
		for(int j=i+1;j<=n;j++)
		{
			
			if(a[i]>a[j])
			{		
				dp1[i]=max(dp1[i],dp1[j]+1);
			}
		}
	}
	for(int i=2;i<=n;i++)
	{
		dp2[i]=1;
		for(int j=1;j<=i;j++)
		{
			if(a[i]>a[j])
			{
				dp2[i]=max(dp2[i],dp2[j]+1);
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,dp1[i]+dp2[i]-1);
	}
	cout<<n-ans;
	return 0;
 } 
 

2.区间dp

很惊讶以前甚至都没有写区间dp的总结。

简而言之,这种dp一般开二维,枚举区间,枚举断点,合并求值。(如 \(dp[i][j]\) 表示从 \(i\) 到 \(j\) 这个区间的极值,最后输出 \(dp[1][n]\) (n为区间长度))

模版代码:

for(int len=1;len<=n;len++)
{
	for(int i=1;i<=n-len+1;i++)
	{
		int j=i+len-1;
		for(int k=i;k<j;k++)
		{
			//状态转移方程
		}
	}
}

例题:

石子合并(弱化版) 强化版

能量项链

一些套路:

  • 基本都有枚举断点、合并的操作。状态转移方程:\(dp[i][j]=dp[i][k]+dp[k][j]\)。
  • 除了上一条之外,还可以从两边的端点扩展,或者同时扩展。具体根据题目改变。状态转移方程:\(dp[i][j]=\max/\min(dp[i+1][j]+a[i],dp[i][j-1]+a[j],dp[i+1][j-1]+a[i]+a[j])\)。
  • 转移的时候往往要分类讨论,或者判断是否合法。注意,像 \(dp[i][j]=min(dp[i][j],dp[i+1][j]+(a[i]==k))\) 这种语句 \((a[i]==k)\) 不能拿出来另外判断!
  • 如果实在难以维护,可以考虑多维护一维/多开一个数组,辅助转移。
  • 有时候预处理能省很多事。
  • 还有一个关路灯型的区间dp,很多题里都有。

总结:区间dp的数据范围一般比较小(甚至有些题 \(O(n^4)\) 也能过),区间转移比较套路。

3.背包dp

直接看吧。。。

背包九讲

如果你还是不理解多重背包的二进制优化,可以看看这篇


4.树形dp

个人认为归纳梳理很清晰
树形dp

大致就是dfs上写dp(可以用链式前向星来存图)

顺带放一下链式前向星的代码:

int head[100005], edgenum;
struct edge{
	int next;
	int to;
	int w;
};
edge edge[MAXN];
void add(int from,int to,int w)
{
	edge[++edgenum].next=head[from];
	edge[edgenum].to=to;
	edge[edgenum].w=w;
	head[from]=edgenum;
}
......
for(int i=head[u];i;i=edge[i].next)
{
	......
}

5.状态压缩dp

这是一个考试可以打暴力分的优化。本质上是dp,通过状态压缩优化,将一些操作改为位运算即可。(注意优先级)

关于位运算的一些知识

二进制位的常用变换

一篇博客

先放个模板题和代码:

P1896 互不侵犯

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, k, ans, len, num;
ll c[10000], dp[10][100][2000], cnt[10000];
int main()
{
	cin>>n>>k;
	for(int i=0;i<(1<<n);i++)
	{
		int s1=i;
		num=0;
		while(s1)
		{
			if(s1&1)
			{
				num++;
			}
			s1>>=1;
		}
		cnt[i]=num;
		if((((i<<1)|(i>>1))&i)==0)
		{
			c[++len]=i;
		}
	}
	dp[0][0][0]=1;                
    for(int i=1;i<=n;i++)         
    {
        for(int d=1;d<=len;d++)   
        {
            int s1=c[d];             
            for(int u=1;u<=len;u++)
            {
                int s2=c[u];
                if(((s2|(s2<<1)|(s2>>1))&s1)==0)  
                {    
                    for(int j=0;j<=k;j++)
                    {
	                   if(j-cnt[s1]>=0)
						{
							dp[i][j][s1]+=dp[i-1][j-cnt[s1]][s2];
						} 	
				   }                                                         
                }
            }
        }
    }
	for(int i=1;i<=len;i++)
	{
		ans+=dp[n][k][c[i]];
	}
	cout<<ans;
	return 0;
}

6.单调队列优化dp

前置知识:单调队列(详见学习笔记

其实它本质上是一个dp,由于时间复杂度的限制,用单调队列优化。

往往我们要求最大值,就把最大值放在队首,维护一个单调递减的队列。反之,亦然。

核心代码:

for(int i=1;i<=n;i++)
{
    if(!q.empty()&&q.front()+m<i)//m:区间长度
	{
		q.pop_front();
	} 
    //状态转移方程 
    while(!q.empty()&&a[q.back()]>a[i])
	{
		q.pop_back();
	} 
    q.push_back(i);
} 

7.斜率优化dp

你猜我为什么没有写 完

似乎这种优化只需要掌握点关于一次函数的知识,实在不知道的bd一下就好了。

进入正题:

它的状态转移方程一般为:\(dp[i]=\min/\max(A+B+C)(A\)表示一个关于\(i\)的式子,\(B\)表示一个关于j的式子,\(C\)是一个存在形如 \(a_{i}*b_{j}\) 的项的式子,例如 \(dp[i]=dp[j]+(i-j)^2\).)

此时这个式子需要采用斜率优化。

做题思路:先用常规dp方法推出状态转移方程,假设存在 \(k\) 比当前选择更优,将两个dp式子列出来比较,进行展开、移项、合并同类项(简称推式子)等方法转换为斜率式子,将较为复杂且下标相同的部分用另一个数组代替(例如:\(f[x]=dp[x]+s[x]^2\)),最终化成形如\((f[j]-f[k])/(s[j]-s[k])<2s[i]\) 的式子。

然后判断要维护一个上凸包还是下凸包,用单调队列来维护。

模板代码:

int slope_up(int j, int k) 
{	
	return dp[j]-dp[k];
}
int slope_down(int j, int k) 
{
	return a[j]-a[k];
}
int main() 
{
	memset(dp, INF, sizeof(dp));
	dp[0]=0; 
	int head=1, tail=0;
	q[++tail]=0;
	for (int i=1;i<=n;i++) 
	{
		while(head<tail&&slope_up(q[head+1],q[head])<=b[i]*slope_down(q[head+1],q[head])) 
		{
			head++;
		}
		//转移方程 
		while(head<tail&&slope_up(q[tail],q[tail-1])*slope_down(i,q[tail])>=slope_up(i,q[tail])*slope_down(q[tail],q[tail-1])) 
		{
			tail--;
		}
		q[++tail]=i;
	}
}

推荐一篇博客:\(Blog\)


\(dp\)方面的优化汇总

点我

tbc.

标签:int,笔记,学习,tail,edge,DP,转移,dp,式子
From: https://www.cnblogs.com/zhouyiran2011/p/18365604

相关文章

  • tarjan之LCA学习笔记
    tarjan之LCA学习笔记tarjan算法求LCA可谓是一个极其巧妙的离线算法其本质是利用DFS遍历时产生的DFS序和并查集来在线性的时间复杂度内求出所有询问的结果既然是离线算法,其和在线算法的区别就在与离线算法需要记录下所有查询,对查询进行一定操作来得到更高的效率,而这......
  • C语言学习————常量和宏、初识指针
    #define定义常量和宏define是一个预处理指令用途:1.define定义符号#defineMAX1000intmain(){ printf("%d\n",MAX); return0;}2.define定义宏#defineADD(X,Y)((X)+(Y))intmain(){ printf("%d\n",ADD(2,3)); return0;}指针内存内存是计算机上特......
  • 【动态规划、dp】[CSP-J 2022] 上升点列 题解
    题目描述在一个二维平面内,给定nnn个整数点(xi......
  • 【防忘笔记】Spring+Struts2古董框架学习
    Spring+Struts2项目框架梳理若基于Spring+Struts2的方式进行开发,前后端的交互逻辑会与boot系以及MCV的组织结构有所不同这里是对于学习过程的一些记录前置通用知识Struts2框架资料Struts2基础篇之基本概念Java之struts2框架学习一般情况的Spring前后端调试流程要理解基于......
  • ssy中学暑假集训有关数学及多项式学习笔记
    8.16日集训倒数第\(7\)天唉,不知不觉间在ssy中学的暑假集训就要结束了,只剩下一周的时间了,然而byn和yzh还有bao学姐\(21\)号就要走了,暑假就要过去了....今天模拟赛的第二题很有意思,涉及到了许多的数学知识,正好来恶补一下:浅谈反演原理和二项式反演首先来说说什么是反演(inversio......
  • FFmpeg开发笔记(四十八)从0开始搭建直播系统的开源软件架构
    ​音视频技术的一个主要用途是直播,包括电视直播、电脑直播、手机直播等等,甚至在线课堂、在线问诊、安防监控等应用都属于直播系统的范畴。由于直播系统不仅涉及到音视频数据的编解码,还涉及到音视频数据的实时传输,因此直播领域采用的网络技术标准比较高,实现起来也比一般的WEB系统复......
  • java基础概念笔记
    java基础概念1.注释分类单行注释://注释信息多行注释:/*注释信息*/文档注释:/**注释信息*/但是一般不用2.关键字2.1关键字的特点关键字的字母全部小写常用的代码编辑器,针对关键字有特殊的颜色标记,非常直观。注意:关键字很多,不用刻意去记。abstracta......
  • 越权漏洞学习-做你做不了的事情
    原文链接:https://blog.csdn.net/weixin_49349476/article/details/131362007(一)、什么是越权漏洞1、了解越权漏洞:越权漏洞是指一个用户或者一个攻击者通过利用系统中某一漏洞,可以获得超过其正常权限的权限。也就是说,越权漏洞会使攻击者能够执行未经授权的操作或访问受保护的资源......
  • 学习-zabbix架构及术语
    Zabbix组成架构ZabbixServerzabbixserver是agent程序报告系统可用性、系统完整性和统计数据的核心组件、是所有配置信息、统计信息和操作数据的核心存储器zabbix数据库存储所有配置信息和zavvix收集到的数据都被存储再数据库中zabbixweb界面为了从任何地方和任何......
  • WebRTC音视频开发读书笔记(一)
    一、基本概念WebRTC(WebReal-TimeCommunication,网页即时通信)于2011年6月1日开源,并被纳入万维网联盟的W3C推荐标准,它通过简单API为浏览器和移动应用提供实时通信RTC功能。1、特点跨平台:可以在Web,Android、IOS、Windows、MacOS、Linux环境运行。实时传输:速度快、延迟低。......