【算法每日一练]-动态规划 （保姆级教程 篇16) #纸带 #围栏木桩 #四柱河内塔

目录

今日知识点：

计算最长子序列的方案个数，类似最短路径个数问题

四柱河内塔问题：dp[i]=min{ (p[i-k]+f[k])+dp[i-k] } 

纸带

围栏木桩

 四柱河内塔

---

        

        
纸带

思路：

我们先设置dp[i]表示从i到n的方案数。

那么减法操作中：i可以移动到[1,i-1]中的任意一个格子。反过来可以认为：i可以从i+1到n转移过来。所以得出dp[i]=dp[i+1]+…dp[n]；（使用后缀和即可）

然后除法操作中：i可以移动到[1,i/2]中的任意一个格子。反过来可以认为：i可以从x/2==i的任意x移动过来。所以得出dp[i]+=sum[i*j]-sum[i*j+j]（i*j<=n）

#include <bits/stdc++.h>
using namespace std;
const int N=4e6+5;
int n,mod,dp[N],sum[N];int main(){cin>>n>>mod;dp[n]=sum[n]=1;for(int i=n-1;i>=1;i--){dp[i]=sum[i+1];//减法for(int j=2;j*i<=n;j++){//除法int r=min(n,i*j+j-1);dp[i]=(dp[i]+sum[i*j]-sum[r+1])%mod;}sum[i]=(sum[i+1]+dp[i])%mod;}	cout<<dp[1];
}

        

         

围栏木桩

 输入：
3
9 10 1 9 8 7 6 3 4 6
3 100 70 102
6 40 37 23 89 91 12

思路：

其实就是先找最长上升子序列，然后再求有多少个最长的上升子序列。

首先设置dp[i]表示以i结尾的最长上升子序列。

转移：（i能拼在j后面的话）dp[i]=max(dp[j])+1;

那么要求有多少个最长上升子序列的话就要进行修改，

把dp[i]=max(dp[j])+1改成 if(dp[j]+1>dp[i]) dp[i]=dp[j]+1;

这样的话就能知道什么时候修改了dp[i]，当修改dp[i]的时候自然是因为i可以拼在j之后且拼完后dp[i]会变大。

故：f[i]=f[j]

当dp[j]+1=dp[i]时候，说明i即便拼在j后面dp也不会变化，那就说明拼在这个j后面也是最优解。

故：f[i]+=f[j]

类似最短路径个数问题嘛！

#include <bits/stdc++.h>
using namespace std;
const int N=27;
int n,m,h[N],dp[N],f[N],ans1,ans2;int main(){cin>>m;while(m--){cin>>n;ans1=0;ans2=0;for(int i=1;i<=n;i++){cin>>h[i];dp[i]=f[i]=1;}for(int i=2;i<=n;i++)for(int j=i-1;j;j--){if(h[j]<=h[i]){if(dp[j]+1>dp[i]){//更新最优解就继承dp[i]=dp[j]+1;f[i]=f[j];}else if(dp[j]+1==dp[i])//当前的j也是可以使变成最优解的jf[i]+=f[j];}}for(int i=1;i<=n;i++)ans1=max(ans1,dp[i]);for(int i=1;i<=n;i++)if(dp[i]==ans1)ans2+=f[i];cout<<ans1<<" "<<ans2<<'\n';}	
}

        

         

 四柱河内塔

思路：

这道题听过的很简单，没见过的确实很难做了。

首先我们从最简单的3柱开始：就如下图，对于n柱的河内塔把第一柱上面n-1个放到中间的柱子上，然后剩下的一个放到最右边，然后就转化成了把n-1个盘子的三柱河内塔问题。

设置dp[i]表示i个盘子的三柱河内塔问题。

那么对应转移方程：dp[i]=(dp[i-1]+1)+dp[i-1]=2*dp[i-1]+1

那么现在来考虑四柱河内塔情况：

对于n个盘子的四柱河内塔，我们先将上面的n-k个放到任意一柱上，然后剩余的k个放到最右边柱子。最后也转化成了n-k个盘子的四柱河内塔问题。

要注意的一点是：在转移k个盘子的情况属于3柱的河内塔问题，因为有一柱是不能使用的。

转移方程:dp[i]=(p[i-k]+f[k])+dp[i-k]  其中f[k]是三柱k个盘子的河内塔问题。dp[i-k]是四柱n-k个盘子的河内塔问题。但是我们并不确定到底是让k取多少，但是我们确定的是k的选值必须使得dp[i]最小。那么就有dp[i]=min{ (p[i-k]+f[k])+dp[i-k] } 

         

下面是代码部分 

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int f,dp[55];
int main(){cin>>f;memset(dp,INF,sizeof(dp));dp[0]=0;dp[1]=1;dp[2]=3;//初始化cout<<1<<'\n'<<3<<'\n';for(int i=3;i<=f;i++){for(int j=1;j<i;j++){if(dp[i]>2*dp[i-j]+pow(2,j)-1)//pow(2,j)-1就是f[j]的值dp[i]=2*dp[i-j]+pow(2,j)-1;}cout<<dp[i]<<'\n';}
}