題意

有高為 1， 2， …， n 的 n 根桿子排成一排， 從左向右能看到 L 根， 從右向左能看到 R 根。求有多少種可能的排列方式。

solution:

數(shù)據(jù)范圍僅200，本來(lái)是往組合數(shù)學(xué)方面想的，看到了這個(gè)200就放棄了念頭，果然是dp

定義dp[i][j][k]是用了高度為1~i的桿子，從左邊能看到j(luò)個(gè)，從右邊能看到k個(gè)

如果從1轉(zhuǎn)移到n很困難，因?yàn)榉乓粋€(gè)高的桿子進(jìn)去會(huì)造成很多的遮擋影響，是幾乎不能維護(hù)的。于是考慮從n轉(zhuǎn)移到1，即先放比較高的桿子

加上放好了2~n高度的桿子，再放高度為1的桿子僅有三種情況

1.放在最左邊。僅僅是從左看能多看到一個(gè) dp[i][j][k]+=dp[i-1][j-1][k]

2.放在最右邊，同理

3.放在中間，一定會(huì)被擋住。i-1根桿子間有（i-2）個(gè)，則dp[i][j][k]+=dp[i-1][j][k]*(i-2)。

其實(shí)這里i的定義已經(jīng)發(fā)生了一點(diǎn)變化，但是狀態(tài)轉(zhuǎn)移是很容易理解的

為什么可以把i等效定義為i個(gè)，而不是1~i呢？其實(shí)這只需要代表是i根高度不同的桿子，2~i的桿子全部砍1，相對(duì)高度沒(méi)有變，也就等效成了1~i-1的桿子

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<queue> 6 #include<cstring> 7 #define mp make_pair 8 #define pb push_back 9 #define first fi 10 #define second se 11 #define pw(x) (1ll << (x)) 12 #define sz(x) ((int)(x).size()) 13 #define all(x) (x).begin(),(x).end() 14 #define rep(i,l,r) for(int i=(l);i<(r);i++) 15 #define per(i,r,l) for(int i=(r);i>=(l);i--) 16 #define FOR(i,l,r) for(int i=(l);i<=(r);i++) 17 #define eps 1e-9 18 #define PIE acos(-1) 19 #define cl(a,b) memset(a,b,sizeof(a)) 20 #define fastio ios::sync_with_stdio(false);cin.tie(0); 21 #define lson l , mid , ls 22 #define rson mid + 1 , r , rs 23 #define ls (rt<<1) 24 #define rs (ls|1) 25 #define INF 0x3f3f3f3f 26 #define LINF 0x3f3f3f3f3f3f3f3f 27 #define freopen freopen("in.txt","r",stdin); 28 #define cfin ifstream cin("in.txt"); 29 #define lowbit(x) (x&(-x)) 30 #define sqr(a) a*a 31 #define ll long long 32 #define ull unsigned long long 33 #define vi vector<int> 34 #define pii pair<int, int> 35 #define dd(x) cout << #x << " = " << (x) << ", " 36 #define de(x) cout << #x << " = " << (x) << "\n" 37 #define endl "\n" 38 using namespace std; 39 //********************************** 40 ll dp[25][25][25];//dp[i][j][k]表示i個(gè)棒子從左邊能看到j(luò)個(gè)右邊能看到k個(gè)的方案數(shù) 41 //********************************** 42 void Init() 43 { 44 dp[1][1][1]=1; 45 FOR(i,2,20)FOR(j,1,i)FOR(k,1,i-j+1)dp[i][j][k]=dp[i-1][j-1][k]+dp[i-1][j][k-1]+dp[i-1][j][k]*(i-2); 46 } 47 //********************************** 48 int main() 49 { 50 Init(); 51 int T;cin>>T; 52 while(T--){ 53 int a,b,c;cin>>a>>b>>c; 54 cout<<dp[a][b][c]<<endl; 55 } 56 return 0; 57 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/klaycf/p/9689467.html

總結(jié)

以上是生活随笔為你收集整理的计数原理，递推，求从左边能看到l个棒子，右边能看到r个棒子的方案数目的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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