今天是钟神讲课，讲台上照旧摆满了冰红茶
目录时间到:
$1. 动态规划
$2. 数位dp
$3. 树形dp
$4. 区间dp
$5. 状压dp
$6. 其它dp
$1. 动态规划：
·以斐波那契数列为例，简单讲一下dp
1)对于斐波那契数列，有f0=0,f1=1,f2=1……fn=fn-1+fn-2
2)在上面的式子中，我们称f0=0为边界条件。推广到动态规划中，我们称不受其它元素的影响的元素为边界条件
3)在上面的式子中，我们称fn=fn-1+fn-2为转移方程
4)在上面的式子中，我们称f1,f2,f3,……,fn为状态
5)说句题外话，斐波那契数列有一个通项公式：
by 百度百科
·动态规划的写法
1)顺着推
2)倒着推
3)记忆化搜索
·以斐波那契数列为例，分别用三个写法写一下代码：
1)顺着推：这是最简单的算法，将转移方程写一下就可以了，这是一种用别人来更新自己的方法（好自私啊
接下来是代码：
#include<cstdio>
#include<iostream>
using namespace std;
int f[],n;
int main()
{
scanf("%d",&n);
f[]=;
f[]=;//对边界条件的判断
for(int i=;i<=n;++i)//从没有值的第二项开始计算
{
f[i]=f[i-]+f[i-];//这就是转移方程
}
printf("%d",f[n]);
return ;
}2)倒着推：这种方法主要是用自己来更新别人的思想（比较大公无私
看一下代码：
#include<cstdio>
#include<iostream>
using namespace std;
int f[],n;
int main()
{
scanf("%d",&n);
f[]=;
f[]=;
for(int i=;i<=n;++i)//这个方法要从1开始循环，因为第一个值可以影响到其他的值
{
f[i+]+=f[i];//当前值可以影响下一个值
f[i+]+=f[i];//当前值也可以影响下两个值
}
printf("%d",f[n]);
return ;
}3)在将记忆化搜索之前，我们先将搜索的代码分析一下
#include<cstdio>
#include<iostream>
using namespace std;
int f[],n; int dfs(int n)
{
if(n==) return ;
if(n==) return ;//相当于对边界条件的判断
return dfs(n-)+dfs(n-);//前两个数的和
} int main()
{
scanf("%d",&n);
printf("%d",dfs(n));
return ;
}这样一来，代码的复杂度将是O(f(n))的，也就是一个指数级的复杂度，那么什么导致了这样的复杂度呢，通过手推可以发现，这个算法对每一个数都不只算了一次，那么我们就可以进行优化。即保存一个判断当前数是否算过的数组，每次算过就标为已算，如果查到的数以前算过，就直接返回这个值，这样就完成了记忆化搜索。值得注意的是，优化之后的算法多开了一个数组，所以所开的空间会相应变大，但是时间复杂度和1)2)没什么区别。
#include<cstdio>
#include<iostream>
using namespace std;
int f[],n;
bool suan_le_mei[];//第i项斐波那契数列有没有被算，由于多开了一个算了没数组，代码所开的空间相应会变大 int dfs(int n)
{
if(n==) return ;
if(n==) return ;
if(suan_le_mei[n]) return f[n];
suan_le_mei[n]=true;
f[n]=dfs(n-)+dfs(n-);
return f[n];
} int main()
{
scanf("%d",&n);
printf("%d",dfs(n));
return ;
}
·动态规划的种类：
1)数位dp
2)树形dp
3)状压dp
4)其他dp（可能性最大的，因为没有套路
5)区间dp
6)插头dp，博弈论dp（NIOP极有可能不考
$2. 数位dp
·首先还是又一个问题引入:读入两个正整数l，r，问从l到r有多少个整数：
a)很显然，这个问题可以用r-l+1这个公式来解决
b)但是为了自找苦吃，神犇zhx要通过数位dp来解决
c)这种做法的核心是算出来0~r中的所有数和0~l-1中的所有数然后用前者减去后者
d)我们可以先求0到x这个区间中有多少个数，写出x的十进制表示：xn，xn-1……x0（x0表示各位），然后一位一位的dp
e)找到有多少个v满足0<=v<=x，v最多有n位（n为x的位数）。这样，问题就转化成了对于vn，vn-1……v0中每一个位置填一个数，求所有满足v<x的方案数
f)填数的方法为从左往右填数，以前三位为例：
当xnxn-1xn-2>vnvn-1vn-2时，vn-3可以随便填（0~9中的数）
当xnxn-1xn-2=vnvn-1vn-2时，vn-3能够填的数只有0~xn-3中的数
g)一般来说，数位dp的状态一般有两个维度f[ i ] [ j ]表示已经填好了前i位，j一般有两个数0,1，分别表示e)中的两种状态，j=0时大于，j=1时等于，f[ i ] [ j ]表示这种情况下方案数是多少
h)方法：枚举第i-1位填什么 ，转移到f[ i-1 ][ j ]；边界条件：第n+1位的值一定都是0，即f[n+1][1]=1（这两个数都填0）
写一下代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int f[][],z[],l,r; int solve(int x)
{
int n=;
while(x)
{
z[n]=x%;
x/=;
n++;
}//存一下x的十进制表示
n--;
memset(f,,sizeof(f));//要做两个动态规划
f[n+][]=;
for(int i=n;i>=;i--)
for(int j=;j<=;++j)
{
if(j==)// xnxn-1xn-2>vnvn-1vn-2时，剩下的从0~9之间随便填
{
for(int k=;k<=;++k)
f[i][]+=f[i+][j];
}
else// xnxn-1xn-2=vnvn-1vn-2时，分两种情况讨论
{
for(int k=;k<=z[i];++k)//只能到当前的xj
{
if(k==z[i]) f[i][]+=f[i+][j];//如果选了xj，代表当前是相等的情况，转移到f[i][1]
else f[i][]+=f[i+][j];//如果没选，代表当前是小于的，转移到f[i][0]的情况
}
}
}
return f[][]+f[][];
} int main()
{
cin>>l>>r;
cout<<solve(r)-solve(l-)<<endl;
return ;
}
·有了这一套代码，其他的数位dp也很好求：
再举一个例子：求在[ L , R ]中数的数位之和，直接上代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int f[][],z[],l,r;
int g[][];//表示数位之和 int solve(int x)
{
int n=;
while(x)
{
z[n]=x%;
x/=;
n++;
}//存一下x的十进制表示
n--;
memset(f,,sizeof(f));//要做两个动态规划
memset(g,,sizeof(g));
f[n+][]=;
g[n+][]=;
for(int i=n;i>=;i--)
for(int j=;j<=;++j)
{
if(j==)
{
for(int k=;k<=;++k)
{
f[i][]+=f[i+][j];
g[i][]+=g[i+][j]+f[i+][j]*k;
}
}
else
{
for(int k=;k<=z[i];++k)
{
if(k==z[i])
{
f[i][]+=f[i+][j];
g[i][]+=g[i+][j]+f[i+][j]*k;
}
else
{
f[i][]+=f[i+][j];
g[i][]+=g[i+][j]+f[i+][j]*k;
}
}
}
}
return g[][]+g[][];
} int main()
{
cin>>l>>r;
cout<<solve(r)-solve(l-)<<endl;
return ;
}
$3. 树形dp
·还是一个例子：
a)给一棵n个点的树，问这棵树有多少个点
b)解释一下：数位dp的苦没吃够，zhx神仙又要在这种读入n输出n的题上找点儿
c)树形dp：
1.众所周知，以根节点为根的子树就是整棵树
2.那么，我们规定f[i]表示以i为根节点的子树的节点个数
3.现在，我们要从f[i]求到f[1]
4.但是，只有叶节点的子树大小可知，且都是1
5.所以得出转移方程：f[p]=f[p1]+f[p2]+……+f[pn]+1
d)由于蒟蒻hqk还没有能力写代码，只有伪代码供大家食用：
#include<iostream>
using namespace std;
int f[]; void dfs(int p)
{
for(x is p'son)//这句话是钟神写的，意思是枚举p的所有儿子
{
dfs(x);
f[p]+=f[x];//转移方程
}
f[p]++;
} int main()
{
read_tree();
dfs();
printf("%d",f[]);
return ;
}
·再来一个例题：
题目：给定一个树，求这棵树的直径是啥
首先解释一下：直径在树中表示是两个点的最长距离，翻译一下，就是找从某个点向上走的最长路径和次长路径；
那么怎么求呢？
可以用f[i][0]表示i向下最长路，f[i][1]表示次长路
这样，转移方程就有了：f[p][0]=max{f[p1][0],f[p2][0],……,f[pn][0]}+1;//求最大值的方程
f[p][1]=max{f[p1][0],……,f[pn][0]}+1//将找到的最大值去掉
这样，这道题的思路就有了，但是蒟蒻hqk连伪代码都不会写，那我们就直接进行下一个----
$4. 区间dp
·又是一个例子：
合并石子：有n堆石子n1,n2,n3……nn，允许合并相邻的石子。合并石子的代价是两堆石子数量的总和。现在将这n堆石头合并为1堆石头，要求代价最小
题目分析：首先f[l][r]表示将第l堆石子到第r堆石子合并为一堆石子的最小代价，
边界条件：l=r时，即f[i][i]=0；
转移方程：最后一次合并一定是将某两堆石子合并为一堆石子，这两堆石头对应了一个分界线，左边和右边分别合并后没有合并的一块，所以就可以写出转移方程：f[l][r]=min{f[l][p]+f[p+1][r]+sum[l][r]};
·这道题的代码：（钟神写的）
#include<cstdio>
#include<iostream>
using namespace std;
int n,z[];
int f[][];
int main()
{
cin>>n;
for(int i=;i<=n;++i)
cin>>z[i];
memset(f,0x3f,sizeof(f))
for(int i=;i<=n;++i)
{
f[i][i]=;
}
for(int len=;len<=n;++len)
for(int l=,r=len;r<=n;++l,++r)
for(int p=;p<r;++r)//O(n^3)的复杂度
f[l][r]=min(f[l][r],f[l][r]+f[p+][r]+sum[l][r]);
cout<<f[][n]<<endl;
}
·区间dp一般思路：枚举一个断点，对断点进行操作
$5. 状压dp
·状压dp是今天讲的最难的一类dp，但是开了窍就好了
·是不是还有一个例题？ 是！
给你n个点（以坐标的形式），一个人在一号点，那么这个人在第一个点出发，在保证每一个点都能走一次，使得走过的路径的长度最短
这道题叫做TSP问题（旅行商问题），这个问题的复杂度最低也是O(n^2)的；
题目分析：从一号点出发，一个点没有必要走两次（每个点只需去一次）；两点之间线段最短；所以我们要知道已经走了哪些点，还没有走哪些点，也就是说，要将没有走过的点一一列举；
核心算法：状压—状态压缩，状态压缩的核心就是构造一个n位的二进制数，n为点的个数，二进制位上的1表示这个元素在这个集合中，0表示这个元素不在这个集合中；例：011001=25表示{1,4,5}这个集合
实现：用f[s][i]来存一个n位的二进制数，s表示已经走过的点所构成的集合，i表示当前停留在的点。初始化（边界条件）f[1][1]=0;
转移：如果j∉s，f[s∪{j}][j]=f[s][j]+dis(i,j)
这样一来，状压dp就完成了（但是代码实现呢？）
别急，这就来：
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=;
int n,x[maxn],y[maxn];
double f[<<maxn][maxn];//1<<maxn相当于2的maxn次方 double dis(int i,int j)
{
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
} int main()
{
cin>>n;
for(int i=;i<n;++i)//二进制的最低位对应的是第0位，而不是第一位
{
cin>>x[i]>>y[i];
}
for(int i=;i<=(<<n);++i)
for(int j=;j<n;++j)
f[i][j]=1e+;
f[][]=;
for(int s=;s<(<<n);++s)//O(n^2•2^n)，能接受的数据范围是在20以内
//n<=12时，直接暴搜
//n<=100,O(n^3)
//n<=1000,O(n^2)
//n<=10^5，数据结构
//n<=10^6,线性做法
//再多一些就只能考虑O(1)的算法
for(int i=;i<n;++i)
{
if(((s>>i)&==))//取出了s的第i位，这句话是用来判断i是否在集合s中
for(int j=;j<n;++j)
if(((s<<j)&)==)//j不在这个集合中
f[s|(<<j)][j]=min(f[s|(<<j)][j],dis(i,j));
}
double ans=1e+;
for(int i=;i<n;++i)
ans=min(ans,f[(<<n)-][i]);
cout<<ans<<endl;
return ;
}
$6. 其它dp
这里就只讲一下思路，代码就不写了
·例（1）
还是数字三角形，但是这个题要求对一个数取模，输出取模后最大的解
这样，我们就无法用1994年IOI的那道题的思路了
那么我们再开一个维度
定义f[i][j][k]代表走到第i行第j列，数据%m为k的情况能否找到
转移方程为;
if(f[i-1][j-1][(k-a[i][j])%m]||f[i-1][j][(k-a[i][j])%m]) f[i][j][k]=true
边界条件为：
f[1][1][a[1][1]%m]==true
·例（2）
还是最长上升子序列，但是这个题的数据范围扩大到了10^5
假设v是a[1]~a[n]的最大值，把这个值存到一个线段树中，所有小于a[i]的值都被放在了a[i]左边，只用到了线段树的单点更改和区间求最值的操作，所以复杂度是O(NlogN)的
·背包问题
好啦，第三天的整理就到这里了（昨天的整理沉了，因为我没有保存好QAQ）