目錄

今日知識點(diǎn)：

計(jì)算最長子序列的方案個(gè)數(shù)，類似最短路徑個(gè)數(shù)問題

四柱河內(nèi)塔問題：dp[i]=min{ (p[i-k]+f[k])+dp[i-k] }?

紙帶

圍欄木樁

?四柱河內(nèi)塔

---

????????

????????
紙帶

思路：

我們先設(shè)置dp[i]表示從i到n的方案數(shù)。

那么減法操作中：i可以移動(dòng)到[1,i-1]中的任意一個(gè)格子。反過來可以認(rèn)為：i可以從i+1到n轉(zhuǎn)移過來。所以得出dp[i]=dp[i+1]+…dp[n]；（使用后綴和即可）

然后除法操作中：i可以移動(dòng)到[1,i/2]中的任意一個(gè)格子。反過來可以認(rèn)為：i可以從x/2==i的任意x移動(dòng)過來。所以得出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

思路：

其實(shí)就是先找最長上升子序列，然后再求有多少個(gè)最長的上升子序列。

首先設(shè)置dp[i]表示以i結(jié)尾的最長上升子序列。

轉(zhuǎn)移：（i能拼在j后面的話）dp[i]=max(dp[j])+1;

那么要求有多少個(gè)最長上升子序列的話就要進(jìn)行修改，

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

這樣的話就能知道什么時(shí)候修改了dp[i]，當(dāng)修改dp[i]的時(shí)候自然是因?yàn)閕可以拼在j之后且拼完后dp[i]會(huì)變大。

故：f[i]=f[j]

當(dāng)dp[j]+1=dp[i]時(shí)候，說明i即便拼在j后面dp也不會(huì)變化，那就說明拼在這個(gè)j后面也是最優(yōu)解。

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

類似最短路徑個(gè)數(shù)問題嘛！

#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]){//更新最優(yōu)解就繼承dp[i]=dp[j]+1;f[i]=f[j];}else if(dp[j]+1==dp[i])//當(dāng)前的j也是可以使變成最優(yōu)解的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';}	
}

????????

?????????

?四柱河內(nèi)塔

思路：

這道題聽過的很簡單，沒見過的確實(shí)很難做了。

首先我們從最簡單的3柱開始：就如下圖，對于n柱的河內(nèi)塔把第一柱上面n-1個(gè)放到中間的柱子上，然后剩下的一個(gè)放到最右邊，然后就轉(zhuǎn)化成了把n-1個(gè)盤子的三柱河內(nèi)塔問題。

設(shè)置dp[i]表示i個(gè)盤子的三柱河內(nèi)塔問題。

那么對應(yīng)轉(zhuǎn)移方程：dp[i]=(dp[i-1]+1)+dp[i-1]=2*dp[i-1]+1

那么現(xiàn)在來考慮四柱河內(nèi)塔情況：

對于n個(gè)盤子的四柱河內(nèi)塔，我們先將上面的n-k個(gè)放到任意一柱上，然后剩余的k個(gè)放到最右邊柱子。最后也轉(zhuǎn)化成了n-k個(gè)盤子的四柱河內(nèi)塔問題。

要注意的一點(diǎn)是：在轉(zhuǎn)移k個(gè)盤子的情況屬于3柱的河內(nèi)塔問題，因?yàn)橛幸恢遣荒苁褂玫摹?/p>

轉(zhuǎn)移方程:dp[i]=(p[i-k]+f[k])+dp[i-k]? 其中f[k]是三柱k個(gè)盤子的河內(nèi)塔問題。dp[i-k]是四柱n-k個(gè)盤子的河內(nèi)塔問題。但是我們并不確定到底是讓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';}
}