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

目录

今日知识点：

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

四柱河内塔问题：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也是可以使变成最优解的j
						f[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';
	}
}

?