动态规划算法与分治法类似,是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。
动态规划做题思路:
-
考虑\(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,通过状态压缩优化,将一些操作改为位运算即可。(注意优先级)
先放个模板题和代码:
#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