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的时间复杂度是

所以应该怎么做呢？

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[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);

        }

    }

}//天书

还是看不懂？再讲一遍。

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

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

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

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];//求和求和

    }

}

求树的重心

定义

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

求树的直径

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

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

四、背包

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

1.01背包

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