Day 5 笔记 dp动态规划

一、动态规划的基本思路

就是用一些子状态来算出全局状态。

特点：

无后效性——狗熊掰棒子，所以滚动什么的最好了

可以分解性——每个大的状态可以分解成较小的步骤完成

dp分为很多种，首先就是区间dp。

一、元素dp

1.例题2：入门

给定一个数，求这个数能最少被多少完全平方数加起来得到。

#include <bits.stdc++.h>

using namespace std;

int count;

inline void func(int num)

{

	int ssqrt;double sqqrt;

	sqqrt=sqrt(num),ssqrt=int(sqqrt);

    delete sqqrt;

	if (ssqrt*ssqrt!=num)

	{

		count++;

		func(num-ssqrt*ssqrt);

	}

	else count++;

}

int main()

{

	int num;

	cin>>num;

	func(num);

	printf("%d",count);

	return 0;

}

这个代码是一个dfs，如果用dp求解，就应该再向下寻找，存在一个数组里，用的是递推而不是递归。

例题3 经典的最长公共子序列

click here to transport a harder one

你以为这个题再dfs就能过？这个例题dfs的时间复杂度是

\[O(n^n)啊!
\]

所以应该怎么做呢？

1.dp做法

dp[i][j]=dp[i−1][j−1]+1⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅s1[i−1]==s2[j−1];

意思是找到了一个公共的字符串，这个字符串的长度就是后面的最长公共子序列的“基础”。

dp[i][j]=max(dp[i−1][j],dp[i][j−1])⋅⋅⋅s1[i−1]!=s2[j−1]；

所以通项公式就又出来了。

\[dp[i][j]=\max(dp[i-1][j],dp[i][j-1]);\space\space\space
if (a[i]==b[i])dp[i][j]=\max()
\]

最后的答案就是dp[len1][len2]。

我们了解一下序列问题的动态规划基本思路：

放一个矩阵表示两个串的某一位，然后就把两个位的某一答案表示成dp[i][j]就行了。

打个板子：

[mode in C++]

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e4+1;

int dp[maxn][maxn],a[maxn],b[maxn];

int m,n;

int main()

{

    cin>>n>>m;

    for (register int i=1;i<=n;i++)

        scanf("%d",&a[i]);

    for (register int i=1;i<=m;i++)

        scanf("%d",&b[i]);

    for (register int i=1;i<=n;i++)

    {

        for (register int j=1;j<=m;j++)

        {

            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

            if (a[i]==b[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);

        }

    }

    printf("%d",dp[n][m]);

}

例4 最长不下降子序列

这个似乎比上面的要简单。

首先我们考虑一下，

2.区间型dp来咯

一般用`dp[i][j]`表示区间`[i，j]`的解。

【板子】最短回文串问题

因为这个题我们是要算1到str.size()的那啥回文字符串，所以很明显是一个区间型的问题。

所以我们的动态转移方程是：

if (str[i]==str[j])dp[i][j]=dp[i-1][j-1];

else dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;

例题：合并石子

合并两个相邻的堆。P1880

for (int len=1;len<n;len++)

{

    for (int i=1;i<=n-len;i++)

    {

    }

}

例题：牢房`P1622`

题目描述

Caima王国中有一个奇怪的*，这个*一共有P个牢房，这些牢房一字排开，第i个紧挨着第i+1个（最后一个除外）。现在正好牢房是满的。

上级下发了一个释放名单，要求每天释放名单上的一个人。这可把看守们吓得不轻，因为看守们知道，现在牢房中的P个人，可以相互之间传话。如果某个人离开了，那么原来和这个人能说上话的人，都会很气愤，导致他们那天会一直大吼大叫，搞得看守很头疼。如果给这些要发火的人吃上肉，他们就会安静点。

输入格式：

第一行两个数P和Q，Q表示释放名单上的人数；

第二行Q个数，表示要释放哪些人。

输出格式：

仅一行，表示最少要给多少人次送肉吃。

我们再次使用用dp[i][j]表示区间[i，j]的犯人代价。

从第一个犯人释放的地方，向外扩展，枚举每一个犯人，滚动形式存储，然后我们就求出来了。

核心Code：

int a[p]={+OO,犯人的位置};

sort(a+1,a+p+1);//将犯人的位置进行排序

for (int len=0;len<=n;len++)

{

    for (int i=1;i<=len-n;i++)

    {

        int j=1+len;

        f[i][j]=0xfffffff;

        for (int k=i+1;k<j;k++)

        {

            f[i][j]=min(minn,f[i][k-1]+f[k+1][j]+a[j+1]-a[j-1]-1-1);

        }

    }

}//天书

还是看不懂？再讲一遍。

首先我们要将犯人的位置进行排序，也就是说sort；
已知dp[i][j]表示从第i个要释放的犯人到第j个要释放的犯人需要的肉（代价），
然后要枚举区间长度(这个区间指的是两个犯人之间)，从这里我们知道了左右端点的位置，分别是i和i+len-1,区间间隔的距离是喂肉的需求。
设置一个断点，从左到右枚举一遍，把最小值搞出来
最后输出dp[1][m]即可。

完整代码：

in mode C++

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

const int maxn=1e4+1;

int a[maxn],dp[maxn][maxn],m,n;

int min(int a,int b)

{

	return a<=b?a:b;

}

int main()

{

	scanf("%d%d",&n,&m);

	for (register int i=1;i<=m;i++)

		scanf("%d",&a[i]);

	a[0]=0,a[m+1]=n+1;

	//最左边的人的左边，假设墙也变成了人

	//最右边的人的右边，假设墙也变成了人

	sort(a+1,a+m+1);

	//排序没说的

	for (register int len=1;len<=m;len++)

	{//最长就n个牢房

		for (register int l=1;l+len-1<=m;l++)

		{//枚举左端点 l,r含义左右端点

			int r=l+len-1;//right point

			dp[l][r]=0xfffffff;

			for (register int k=l;k<=r;k++)

			{//从左到右枚举断点k

				dp[l][r]=min(dp[l][r],dp[l][k-1]+dp[k+1][r]+a[r+1]-a[l-1]-1-1);

			}

		}

	}

	printf("%d",dp[1][m]);

	return 0;

}

二、树形 dp

研究完了线段型天书，那么来看看树形数据结构的天书......

树形的动态规划一般是从上到下或者从下到上，

然后用f[i]表示以i为节点的子树或叶子的答案。

f[i]的值用的是儿子的值去更新，然后如果从上到下就用void dfs(int i)或者转成二叉树放进树状数组里,从下到上就用并查集int fa[i],value[i],sum[i]+前向星。

void dfs(int x,int fa)

{//↓,不常用

    f[x]=a[x],g[x]=0;

    for (int i=first[i];~i;i=nxt[x])

    {

        if (v[i]==fa)continue;

        dfs(v[i],x);

        f[x]+=g[v[i]],g[x]+=f[v[i]];

    }

}

void dfs(int x,int fa)

{//↑

    f[x]=f[fa]+a[x];

    for (int i=first[x];~i;i=nxt[i])

    {

        if (v[i]!=fa)dfs(v[i],x);

    	f[x]+=v[x];

    }

}

更新x的和？选or 不选问题。

void dfs(int x,int fa)

{//↑

    f[x]=f[fa]+a[x];

    for (int i=first[x];~i;i=nxt[i])

    {

        f[fa]+=g[v[i]];g[fa]+=f[v[i]];

    }

}

例题：如何给一棵树涂颜色，使得相邻节点的颜色不相同，输出方案数%19260817

void dfs(int x,int fa)

{

    for (int i=1;i<=m;i++)

        fa[x][i]=1;

    for (int i=p[x];~i;i=nxt[i])

    {

        if (v[i]==fa)continue;

        dfs(v[i],x);

        for (int k=1;k<=m;k++)

        {

            if (j!=k)sum+=f[v[i]][k];//每个节点处有几个方案

        }

        f[i][j]*=sum;//把答案乘起来

    }

}

三、数列差分

就是说有一个线段l到r，然后如果在其中所有的点都+c，那么我们就在l点打一个tag，r点后面那个店打一个-c,

如果是树，就这样打标记差分：

Day 5 笔记 dp动态规划

如果求和，情况就会如下图所示：

Day 5 笔记 dp动态规划

int u[maxn],v[maxn],a[maxn]...;

for (int i=1;i<=m;i++)

{//打标记过程

    a[u[i]]+=c[i],a[v[i]]+=c[i];

    a[lca(u[i],v[i])]-=c[i];//给lca打上标记

    a[fa[lca(u[i],v[i])]]-=c[i];//给fa[lca]打上标记

}

void dfs(int x,int fa)

{//子树求和操作

    f[x]=a[x];//先把自己的值加上

    for (int i=first[x];~i;i=nxt[x])

    {

        dfs(v,x);

        f[x]+=f[v];//求和求和

    }

}

求树的重心

定义

Day 5 笔记 dp动态规划

删除树的重心后让最大的剩下的形成的图最大的节点数最小。

求树的直径

求经过i的一条最长的路径

求不一定经过i的一条最长的路径

四、背包

基本思路是开一个数组表示容量是i的时候结果是dp[i],

1.01背包

基本转移方程是dp[j]=max(dp[j],dp[j-c[i]]+v[i]);

\[ {}
时间复杂度:O(mn) 空间复杂度：S(m)
$$ {}
优化一共有两个：

> 一个是滚动一维，可以证明一定滚动完成后是最大解。
>
> 另一个是从0到`c[i]-1`的枚举是废的，只需要枚举`c[i]`到m就行。

需要注意，倒着枚举反而更加稳定。

不说，直接上代码

```cpp
memset(dp,0,sizrof(dp));//全部清0
for (int i=1;i<=n;i++)//有n个物品
for (int j=m/*空间最大有m*/;j>=c[i];j--)//倒着更新，效果更好
max(dp[j],dp[j-c[i]]+v[i]);
```

#### 2.完全背包

完全背包`dp[i][j]`只考虑前一件物品的最大价值。

这里正向枚举会比倒叙枚举更稳定。

```cpp
memset(dp,0,sizrof(dp));//全部清0
for (int i=1;i<=n;i++)//有n个物品
for (int j=c[i]/*空间最大有m*/;j<=m;j++)//倒着更新，效果更好
max(dp[j],dp[j-c[i]]+v[i]);
```

#### 3.多重背包

就是01背包中1个东西变成固定个东西。

二进制分组步骤：

```cpp
int t=1;
while (t<k)
{
printf("%d",t);
k-=t;
t<<=1;
}
if (k-t>0)
print("%d",k-t);
```

分组的意义在于分解转换成01背包。

```cpp
int cnew[]={...新的01背包的物品大小...},wnew[]={...新的01背包的物品价值...};
int o=0;//假设
for (int i=1;i<=n;i++)
{
int y=1;
while (y<t[i])
{
cnew[++o]=y*c[i];
wnew[o]=y*w[i];
t[i]-=y;
y<<=1;
}
if(t[i]>0)
cnew[++o]=t[i]*c[i],wnew[o]=t[i]*w[i];
}//转换成01背包。
```

#### 3.~~混合背包~~

~~真·难受~~

只需要再转换成01就好了

### 五、记忆化搜索

另一种dp形式，利用dfs，是用dp和dfs的手牵手最好使用。

~~看个例题~~

> ### 滑雪

![](https://s2.ax1x.com/2019/02/01/k3yWvD.md.png)

```cpp
//代码恐怕更好理解
const int px[4]={-1,0,1,0},py[4]={0,1,0,-1};
int a[maxn][maxn]
int dfs(int x,int y)
{//求f[x][y]的值
if (f[x][y]!=0)return f[x][y];
for (int i=0;i<4;i++)
{
int nx=x+px[i],ny=y+py[i];
if (a[nx][ny]>=a[x][y])continue;
f[x][y]=max(f[x][y],dfs(nx,ny)+1);
}
return f[x][y];
}
```

~~再来一个~~

> ~~BZOJ~~1079

![](https://s2.ax1x.com/2019/02/01/k364zT.md.png)

~~这个题不记忆化过不去~~

```cpp
int dp[maxn][maxn][maxn][maxn]/*[maxn]*/[11][51];
dp[a][b][c][d][e][i][5]=dp[a-1][b][c][d][e][i-1][2,3,4,5];
void dfs()
```

### 五、其它

#### 1.四边形不等式

若`w[i][j]=w[i-1][j]+w[i][j-1]+f(i,j)`,应当\]

秒客网

Day 5 笔记 dp动态规划

Day 5 笔记 dp动态规划

一、动态规划的基本思路

一、元素dp

1.例题2：入门

例题3 经典的最长公共子序列

1.dp做法

例4 最长不下降子序列

2.区间型dp来咯

一般用`dp[i][j]`表示区间`[i，j]`的解。

【板子】最短回文串问题

例题：合并石子

例题：牢房`P1622`

题目描述

输入格式：

输出格式：

二、树形 dp

例题：如何给一棵树涂颜色，使得相邻节点的颜色不相同，输出方案数%19260817

三、数列差分

求树的重心

定义

求树的直径

求经过i的一条最长的路径

求不一定经过i的一条最长的路径

四、背包

1.01背包

相关文章

Day 5 笔记 dp动态规划

Day 5 笔记 dp动态规划

一、动态规划的基本思路

一、元素dp

1.例题2：入门

例题3 经典的最长公共子序列

1.dp做法

例4 最长不下降子序列

2.区间型dp来咯

一般用dp[i][j]表示区间[i，j]的解。

【板子】最短回文串问题

例题：合并石子

例题：牢房P1622

题目描述

输入格式：

输出格式：

二、树形 dp

例题：如何给一棵树涂颜色，使得相邻节点的颜色不相同，输出方案数%19260817

三、数列差分

求树的重心

定义

求树的直径

求经过i的一条最长的路径

求不一定经过i的一条最长的路径

四、背包

1.01背包

相关文章

一般用`dp[i][j]`表示区间`[i，j]`的解。

例题：牢房`P1622`