辣鸡动态规划毁我青春~~
动态规划中的基本概念
状态：要算什么
转移方程：如何去算
无后效性：把状态看做一个点，转移过程看作一条边，动态规划的所有概念组成了一个有向无环图（(DAG)），所以在做题时一定要考虑是不是满足无后效性
一旦出现乱序的情况，应该对这个图先进行一个拓扑排序
背包问题
有(N)个物品，有一个(M)溶剂的包，每个物品有一个体积和价值，要求最大化价值之和
第(i)个物品的价值为(V_i)，占(W_i)的空间
(dp[i][j])表示已经放好了前(i)个物品，现在放进去的物品的体积之和为(j)。
考虑转移方程：
第(i+1)个物品只有两种情况：放入背包与不放入背包
如果放入第(i+1)个物品，体积不变，价值也不变
如果不放入第(i+1)个物品，应该转移为(dp[i+1][j+V_{i+1}])
现在对于每一个物品就只有放和不放两种情况（这是用自己更新别人的方法）
如果用别人更新自己呢？
对于(dp[i][j])，如果第(i-1)个物品没有放，是由(dp[i-1][j])转移而来的
否则就是由(dp[i-1][i-V_i])更新而来的（加上(W_i)）
代码如下：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[10010][10010];
int w[10010],v[10010];
int n,m;
int ans=0;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;++i)
for(int j=0;j<=m;++j)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i])
dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
}
for(int i=0;i<=m;++i)
ans=max(ans,dp[n][i]);
printf("%d",ans);
return 0;
}
现在每个物品可以用无限次，这个时候要怎么办呢？
直接枚举每个物品用多少次就行了
但是复杂度太高(Omega omega Omega)
我们只需要将原来的(dp[i-1][j-v_i]+w_i)变为(dp[i][j-v_i]+w_i)就好了
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[10010][10010];
int w[10010],v[10010];
int n,m;
int ans=0;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d%d",&v[i],w[i]);
/*for(int i=1;i<=n;++i)
for(int j=0;j<=m;++j)
for(int k=0;k*v[i]<=j;++k)
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
}*/
for(int i=1;i<=n;++i)
for(int j=0;j<=m;++j)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i])
dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
}
for(int i=0;i<=m;++i)
ans=max(ans,dp[n][i]);
printf("%d",ans);
return 0;
}
那如果每个物品只能用有限次，那怎么办呢
还是直接枚举每个物品用多少次就行了
这个东西的复杂度是(O(n^3))的
那么如何优化呢？（有点难）
有限背包最慢的地方是枚举每个物品用了多少次
思想就是将一个背包变成多个捆绑包（进行二进制分解，如果不够了，就只能委屈一下最后一个捆绑包了），然后就变成了一个(01)背包
以(13)为例，可以拆成：(1)、(2)、(4)、(6)四个捆绑包
代码如下（主要是拆捆绑包的部分）
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[10010][10010];
int w[10010],v[10010];
int n,m;
int ans=0;
int main()
{
scanf("%d%d",&n,&m);
int cnt=0;
for(int i=1;i<=n;++i)
{
int v_,w_,z;
scanf("%d%d%d",&v_,&w_,&z);
int x=1;
while(x<=z)
{
cnt++;
v[cnt]=v_*x;
w[cnt]=w_*x;
z-=x;
x*=2;
}
if(z>0)
{
cnt++;
v[cnt]=v_*z;
w[cnt]=w_*z;
}
}
for(int i=1;i<=cnt;++i)
for(int j=0;j<=m;++j)
{
dp[i][j]=dp[i-1][j];
if(j>=v[i])
dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
}
for(int i=0;i<=m;++i)
ans=max(ans,dp[n][i]);
printf("%d",ans);
return 0;
}
基础(DP)
例题一 数字三角形：
状态：(dp[i][j])表示走到第(i)行第(j)列时所走的路径的最大值
状态转移方程：(dp[i][j]=max(dp[i-1][j-1],f[i-1][j])+a[i][j])
例题二 数字三角形：
诶诶，怎么还是水三角形？？？
现在求的是答案对(100)取模之后的最大值
怎么做呢？
钟皓曦：维度不够加一维，维度不够再加一维，你总有一天会过的
状态：布尔状态，(dp[i][j][k])表示走到第(i)行第(j)列的数对(100)取模等于(k)是不是可行的
状态转移：考虑用自己更新别人，由(dp[i][j][k])可以转移到(dp[i+1][j][(a[i+1][j]+k)mod 100])和(dp[i+1][j+1][(a[i+1][j+1]+k)mod 100])
代码如下：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
bool dp[233][233][233];
int n;
int a[233][233];
int ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
scanf("%d",&a[i][j]);
dp[1][1][a[1][1]%100]=true;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
for(int k=0;k<100;++k)
if(dp[i][j][k])
{
dp[i+1][j][(k+a[i][j])%100]=true;
dp[i+1][j+1][(k+a[i+1][j+1])%100]=true;
}
for(int i=1;i<=n;++i)
for(int j=0;j<100;++j)
if(dp[n][i][j]) ans=max(ans,j);
printf("%d",ans);
return 0;
}
例题三 最长上升子序列：
状态：(dp[i])表示以(i)结尾的最长上升子序列的长度
状态转移：(f[i]=max(f[j])+1)满足(1leq j<i)并且(a[j]<a[i])
这个算法复杂度是(O(n^2))的
如果数据再大一点，就可以用线段树
区间(DP)
例题一 合并石子：
把两对相邻的石子合并为一堆石子，每次合并的代价就是两堆石子的个数之和，现在问把(n)堆石子合并为(1)堆石子的最小代价是多少
我们可以发现每次合并是将一段区间的石子合并
这就是一个区间(DP)
区间(DP)的状态一般为(dp[l][r])
状态：$dp[l][r] (表示)[l,r](区间合并的最小代价（)dp[l][l]=0$）
每次都可以在区间中找到一个分界线，最后合并分界线两边的区间
那么就可以枚举分界线(p)
状态转移：(dp[l][r]=min(dp[l][r],dp[l][p]+dp[p+1][r]+sum[r]-sum[l-1])
例题二 无题
把一排矩阵排排坐，保证矩阵是可以相乘得到一个结果的，现在在这几个矩阵中加上括号，使得运算次数最小
状态：(dp[l][r])表示将第(l)个矩阵和第(r)个矩阵的最小运算次数
状态转移：(dp[l][r]=min(dp[l][p]+f[p+1][r]+a[l] imes a[p+1] imes a[r+1]))，(p)是中点。
状压(DP)
例题一 旅行商问题
在平面上由(n)个点，给出每个点的坐标，现在由(1)号点出发，把所有点都走一遍然后回到(1)号点，求最短距离
首先，一般来说我们没有必要把一个点走两次
当前在哪个点、走过了那个点是两个变化的量
状态：(dp[s][i])中(i)表示现在走到了第(i)个点，(s)表示走过了那些点
理论上来说，(s)是要用一个数组来维护的，但是我们现在要用一个数来表示
那么我们就可以用一个二进制数来表示哪些点没走，哪些点走了（(1)表示走过，(0)表示没走过）
状压(DP)能解决的范围在(nleq 20-22)，因为复杂度为(O(2^n imes n^2))
可爱的代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
double dp[233][233];
double x[233],y[233];
double ans=0x3f;
int n;
double dis(int xx,int yy)
{
return sqrt((x[xx]-x[yy])*(x[xx]-y[yy])+(y[xx]-y[yy])*(y[xx]-y[yy]));
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;++i)
scanf("%lf%lf",&x[i],&y[i]);
memset(dp,0x3f,sizeof(dp));
dp[1][0]=0;
for(int s=0;s<(1<<n);s++)
for(int i=0;i<n;++i)
if(dp[s][i]<0x3f)//这是一个可行的方案
{
for(int j=0;j<n;++j)
if((s>>j)&1==0)//将s二进制的第j为取了出来
{
int news=s|(1<<j);//把s的第j为变成了1
dp[news][j]=min(dp[news][j],dp[s][i]+dis(i,j));
}
}
for(int i=0;i<n;++i)
ans=min(ans,dp[(1<<n)-1][i]+dis(i,0));
printf("%d",ans);
return 0;
}
例题二 玉米田
(JOHN)要在一片牧场上种草，每块草坪之间没有相邻的边
状态：(dp[i][s])表示前(i)行的草都种完了，(s)表示第(i)行的草种成了什么样，这种情况下的方案数为(dp[i][s])
考虑第(i+1)行如何种草：
首先第(i+1)行种的草没有两个连续的
其次第(i)行的草和第(i+1)行的草没有相邻的草，就是(s)&(s)'=(0)
例题三 (K)国王问题
在(N imes N)的棋盘中，放(k)个国王，使这些国王不能相互攻击到对方（国王的攻击范围就是其周围的(8)个格子）
参照上一道题（种国王）
状态：(dp[i][s])表示前(i)行的国王都种完了，(s)表示第(i)行的国王种成了什么样，这种情况下的方案数为(dp[i][s])
但是这个题要多放一个国王，所以我们要多加一个维度
新状态：(dp[i][s][j])表示前(i)行的国王都种完了，(s)表示第(i)行的国王种成了什么样，现在放了(j)个国王，这种情况下的方案数为(dp[i][s])
数位(DP)
是在(DP)的过程中按照数的位数进行转移的
例题一 无题
给出两个数(l、r)，求这之间有多少个数
首先，([l,r])之间有多少数，就是求([0,l])和([0,r])之间分别有多少数，然后相减
数位(DP)，就是将一个(n)位数，抽象为(n)个格子，如果要求有多少个数小于这个数，可以用数字填满这(n)个格子
注意：一定要从高位向低位一位一位的填
状态：(dp[i][j])中，已经填好了前(i)位，(j=0)表示当前这个数一定小于(x)，(j=1)表示当前这个数不确定是否小于(x)
状态转移：数位(DP)的转移都是去枚举下一位填什么数
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int l,r;
int dp[10010][10010];
int z[10010];
int solve(int x)
{
int l=0;
while(x>0)
{
l++;
z[l]=x%10;
x/=10;
}
memset(dp,0,sizeof(dp));
dp[l+1][1]=1;//在第l+1位之后都只能填0
/*转移考虑用自己去更新别人*/
for(int i=l+1;i>=2;i--)
for(int j=0;j<=1;++j)
for(int k=0;k<=9;++k)//枚举应该填哪一个数
{
if(j==1&&k>z[i-1]) continue;
int j_;
if(j==0)
j_=0;
else if(k==z[i-1])
j_=1;
else
j_=0;
dp[i-1][j_]+=dp[i][j];
}
return dp[1][0]+dp[1][1];
}
int main()
{
scanf("%d%d",&l,&r);
printf("%d",solve(r)-solve(l-1));
return 0;
}
例题二 无题
求([l,r])中所有数的数位之和
同样，我们可以转化为([0,r])和([0,l-1])之间有的数位之和
状态：(dp[i][j])表示第(i)位已经填完了，(j=0)表示当前这个数一定小于(x)，(j=1)表示当前这个数不确定是否小于(x)，这时的方案数
例题三 无题
求([l,r])中有多少个相邻两位数字之差大于等于(2)的数
状态：$ dp[i][j][k](表示当前已经填了)i(个数，)j=0(表示当前这个数一定小于)x(，)j=1(表示当前这个数不确定是否小于)x(，第)i(位填的数是)k$
例题四 无题
求([l,r])中满足各位数字之积位(k)的数有多少个
状态：(dp[i][j][r])表示当前已经填了(i)个数，(j=0)表示当前这个数一定小于(x)，(j=1)表示当前这个数不确定是否小于(x)，当前乘积为(r)
有些(r)是永远不会用到的，就是那些大于(10)的质数的倍数
新状态：(dp[i][j][a][b][c][d])表示当前已经填了(i)个数，(j=0)表示当前这个数一定小于(x)，(j=1)表示当前这个数不确定是否小于(x)，现在的乘积为(2^a+3^b+5^c+7^d)
树形(DP)
例题一 无题
现在给你一棵(n)个点的树，问这个树有多少点？？？
树形(DP)一般是(DP)以这个点为根的子树的状态
状态：(f[i])表示以(i)为根的树有多少个点
状态转移：(f[i]=sum_{jin})
例题二 无题
给出一棵树，求出树的直径
将两个点的路径看做由(LCA)向下的两条路径
状态：(f[i][0])表示第(i)个点向下的最大值，(f[i][1])表示最小值
状态转移：(f[i][0]=max(f[p_j][0])+1)，(f[i][1])的值应该是剩下的所有儿子的最长路中的最长路
#include<cstdio>
#include<iostream>
using namespace std;
void dfs(int i)
{
for(p is i's son)//教大家如何写伪代码，你只需要boomboomboom，然后boomboomboom，就能boomboom了
dfs(p);
for(p is i's son)
{
int v=f[p][0];
if(v>f[i][0])
{
f[i][1]=f[i][0];
f[i][0]=v;
}
else if(v>f[i][1])
f[i][1]=v;
}
}
int main()
{
scanf("%d",&n);
du ru jian shu;
dfs(1);//强行令1号点为根
return 0;
}
例题三 无题
求所有点之间的路径之和为多少
状态：(dp[i])表示以(i)为根的子树有多少个点
例题四 无题
状态：(dp[i][0/1])表示到了第(i)个点，(1)表示选了改点，(0)表示没有选
如果有一个点选了，那么这个点的所有儿子都不能选
即：(dp[i][1]=sum_{jin son_i}dp[j][0]+a[i])
(dp[i][0]=sum_{jin son_i}max(dp[j][0],dp[j][1]))
例题五 无题
每个士兵可以守护所有与该结点直接相邻的边，请问在所有边都被守护的条件下，最少要安排多少士兵？
状态：(dp[i][0/1])表示以(i)为根的子树的所有点都被守护，(1)表示有士兵，(0)表示没有，此时的最少士兵
(f[i][0]=sum_{jin son_i}dp[i][1])
(dp[i][1]=sum_{jin son_i}max())