zoj 3747
題意：給n個(gè)士兵排隊(duì)，每個(gè)士兵三種G、R、P可選，求至少有m個(gè)連續(xù)G士兵，最多有k個(gè)連續(xù)R士兵的排列的種數(shù)。

都轉(zhuǎn)化為至多的士兵連續(xù)的個(gè)數(shù)。
令集合A={至多n個(gè)G士兵連續(xù)，且至多K個(gè)R士兵連續(xù)}
集合B={至多m-1個(gè)G士兵連續(xù)，且至多K個(gè)連續(xù)的R士兵連續(xù)}
C=A-B={至少m個(gè)士兵連續(xù)，且至少連續(xù)K個(gè)士兵連續(xù)}。

在轉(zhuǎn)化要如何求 至多x個(gè)G士兵連續(xù)，至多y個(gè)士兵連續(xù)
dp[i][0]至多i個(gè)G 的方案數(shù)
dp[i][1]至多i個(gè)R 的方案數(shù)
dp[i][2]第i個(gè)為P 的方案數(shù)

對(duì)G士兵遞推：
? ? 當(dāng)i<=x時(shí)
? ? dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
? ? 當(dāng)i=x+1時(shí)候
? ? dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-1; 減去的是x+1位置為G士兵的時(shí)候
? ? 當(dāng)i>x+1的時(shí)候
? ? dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]-dp[i-x-1][1]-dp[i-x-1][2]; 此時(shí)要減去i前面已經(jīng)出現(xiàn)連續(xù)u個(gè)G的情況，即從i-u到i-1這一段都是G，
那么i-1-u的位置可以是P或者R，
對(duì)士兵R遞推：
同理
?

#include <bits/stdc++.h> #include <iostream> #define X 10005 #define inf 0x3f3f3f3f #define PI 3.141592653589793238462643383 #define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; typedef long long ll; const ll mod=1e9+7; const int maxn=1e6+10; ll dp[maxn][4]; int n,m,k; ll solve(int x,int y)//dp[i][0]至多i個(gè)G dp[i][1]至多i個(gè)R dp[i][2]第i個(gè)為P {dp[0][0]=1;dp[0][1]=dp[0][2]=0;for(int i=1;i<=n;++i){ll ans=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%mod;dp[i][2]=ans;if(i<=x)dp[i][0]=ans;if(i==x+1)dp[i][0]=(ans-1+mod)%mod;if(i>x+1)dp[i][0]=(ans-dp[i-x-1][1]-dp[i-x-1][2]+mod)%mod;if(i<=y)dp[i][1]=ans;if(i==y+1)dp[i][1]=(ans-1+mod)%mod;if(i>y+1)dp[i][1]=(ans-dp[i-x-1][0]-dp[i-x-1][2]+mod)%mod;}return (dp[n][0]+dp[n][1]+dp[n][2])%mod; } int main() {while(cin>>n>>m>>k){cout<<((solve(n,k)-solve(m-1,k))%mod+mod)%mod<<endl;}return 0; }

?

uva10328??Coin Toss(計(jì)數(shù)問(wèn)題）

就是拋硬幣正面為H，反面為T，問(wèn)拋n次的所有可能情況中連續(xù)H的個(gè)數(shù)至少為k的個(gè)數(shù)。

比起那個(gè)zoj3738這道題算是比較好想了，不過(guò)是同一種類型的題目，
dp[i][0]表示前i個(gè)正面朝上的方案總數(shù)，且第i個(gè)為正面朝上，且朝上的個(gè)數(shù)不超過(guò)k個(gè)
dp[i][1]為第i個(gè)位反面朝上,且前i個(gè)朝上的個(gè)數(shù)不超過(guò)k個(gè)
那么題目就求出最多n個(gè)朝上的總方案數(shù)-最多k-1個(gè)正面朝上的總方案數(shù)
不過(guò)和他的兄弟題目zoj 3738 在 dp[0][0]=1或者=0的時(shí)候我有點(diǎn)迷

另一個(gè)思路：鏈接
設(shè)f[i][j]表示拋第i個(gè)硬幣時(shí)連續(xù)的H不超過(guò)j個(gè)的情況總數(shù)，那么由于第i個(gè)可以為正可以為負(fù)，因此不妨先寫成f[i][j]=2*f[i-1][j]。
但是這么寫有些情況下是不正確的，什么情況呢？就是前面i-1個(gè)硬幣的最后j個(gè)全是H，那么第i個(gè)如果再是H的話，總長(zhǎng)度就變成j+1了。
在減去這部分的種數(shù)的時(shí)候，我們要分情況討論一下。如果i==j+1，那么就只有一種情況可以出現(xiàn)j+1個(gè)H，就是i個(gè)硬幣全部是H，因此減去1即可。如果i>j+1，那么如果第i個(gè)硬幣前面有j個(gè)H的話，那么第i-j-1個(gè)硬幣必然應(yīng)該是T，否則H的連續(xù)的數(shù)量就會(huì)超過(guò)j，這種情況就不可能包含在f[i-1][j]里面了，
? ? 因此，我們這時(shí)只要減去一個(gè)f[i-j-2][j]即可。
? ? 最后結(jié)果顯然應(yīng)該是輸出f[n][n]-f[n][k-1]。

#include <bits/stdc++.h> #include <iostream> #define X 10005 #define inf 0x3f3f3f3f #define PI 3.141592653589793238462643383 #define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; typedef long long ll; const ll mod=1e9+7; const int maxn=1e6+10; ll dp[maxn][2]; ll solve(int n,int k) {memset(dp,0,sizeof(dp));dp[0][0]=0,dp[0][1]=1;for(int i=1;i<=n;++i){ll ans=dp[i-1][0]+dp[i-1][1];dp[i][1]=ans;if(i<=k)dp[i][0]=ans;if(i==k+1) dp[i][0]=ans-1;if(i>k) dp[i][0]=ans-dp[i-k-1][1];}return dp[n][0]+dp[n][1]; } int main() {int n,k;while(cin>>n>>k){cout<<solve(n,n)<<endl;cout<<solve(n,n)-solve(n,k-1)<<endl;}return 0; }

HDU 4489
求n個(gè)人按照低高低或者高低高的順序排列種數(shù)是多少
The king has guards of all different heights. Rather than line them up in increasing or decreasing height order, he wants to line them up so each guard is either shorter than the guards next to him or taller than the guards next to him (so the heights go up and down along the line). For example, seven guards of heights 160, 162, 164, 166, 168, 170 and 172 cm. could be arranged as:

or perhaps:

The king wants to know how many guards he needs so he can have a different up and down order at each changing of the guard for rest of his reign. To be able to do this, he needs to know for a given number of guards, n, how many different up and down orders there are:
For example, if there are four guards: 1, 2, 3,4 can be arrange as:
1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423
? ? ?For this problem, you will write a program that takes as input a positive integer n, the number of guards and returns the number of up and down orders for n guards of differing heights.

Input
The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set consists of single line of input containing two integers. The first integer, D is the data set number. The second integer, n (1 <= n <= 20), is the number of guards of differing heights.
Output

For each data set there is one line of output. It contains the data set number (D) followed by a single space, followed by the number of up and down orders for the n guards.

Sample Input
4 1 1 2 3 3 4 4 20
Sample Output
1 1 2 4 3 10 4 740742376475050
?

參考：鏈接
題意：求n個(gè)人按照低高低或者高低高的順序排列種數(shù)是多少
把n個(gè)人的身高設(shè)為1~n， 然后從低到高插入隊(duì)列。 那么將第i個(gè)人插入隊(duì)列的時(shí)候就出現(xiàn)了問(wèn)題， 插入的這個(gè)位置需要滿足前面兩個(gè)是高低， 后面兩個(gè)是低高。
所以我們用DP來(lái)記錄。 用d[i][0] 表示i個(gè)人的隊(duì)列， 結(jié)尾為高低的方法數(shù)， d[i][1]表示開(kāi)頭為低高的方法數(shù)。 ?那么假設(shè)將第i個(gè)人插入， 插入的位置前面有j個(gè)人， 后面有i - 1 - j個(gè)人， 那么當(dāng)前方法數(shù)就累加d[j][0] * d[i-1-j][1] * c[i-1][j]。 最終求得的是有i個(gè)人的時(shí)候的所有方法數(shù)，

那么怎么遞推DP數(shù)組d[i][1] 和 d[i][0] 呢，因?yàn)殚_(kāi)始為低高和結(jié)尾為高低的方法數(shù)相同且各占總方法數(shù)的一半
證明：
當(dāng)n為偶數(shù)時(shí)：假設(shè)高低開(kāi)始的序列為1010.那么把它倒置一下就變成了0101了
也就是說(shuō)每一個(gè)1打頭的對(duì)應(yīng)著一個(gè)0打頭的

當(dāng)n為奇數(shù)時(shí)：假設(shè)波峰開(kāi)始的序列為10101.
假設(shè)第一個(gè)數(shù)大于最后一個(gè)數(shù)，那我們把序列最后一個(gè)數(shù)放到最前序列就變成01010.
如果第一個(gè)數(shù)小于最后一個(gè)數(shù)把第一個(gè)數(shù)放到最后就行了
?

#include <bits/stdc++.h> #include <iostream> #define X 10005 #define inf 0x3f3f3f3f #define PI 3.141592653589793238462643383 #define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; typedef long long ll; const ll mod=1e9+7; const int maxn=1e6+10; ll dp[50][2]; ll c[50][50]; int pos,n; void init() {for(int i=1;i<=20;++i){c[i][0]=c[i][i]=1;for(int j=1;j<i;++j)c[i][j]=c[i-1][j]+c[i-1][j-1];}dp[0][1]=dp[0][0]=1;dp[1][0]=dp[1][1]=1;ll cur=0;for(int i=2;i<=20;++i){cur=0;for(int j=0;j<i;++j)cur+=dp[j][0]*dp[i-j-1][1]*c[i-1][j];dp[i][1]=dp[i][0]=cur/2;} } int main() {init();int t;cin>>t;while(t--){cin>>pos>>n;if(n==1){ cout<<pos<<' '<<1<<endl;continue;}cout<<pos<<' '<<dp[n][0]+dp[n][1]<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【递推DP+加深】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。