題目鏈接：CSAPC08臺灣邀請賽_T1_skyline

題目描述

一座山的山稜線由許多片段的45度斜坡構(gòu)成，每一個片段不是上坡就是下坡。
/
/? * / ?/ * /? // ?/ // / 在我們眼前的所見的任何寬度為n個單位的山稜形狀，可以輕松地觀察到所有山頂?shù)奈恢谩?/p>

請問有多少種山稜線的形狀，使得所有山頂?shù)奈恢糜勺蠖曳沁f減呢？

所有的山稜線都必須完整，也就是說左右兩端都必須是高度為0的山腳，而且不能有任何山谷的位置隱沒在地平線底下。

輸入輸出格式

輸入格式

輸入僅包含一個數(shù)字n，n一定會是偶數(shù)，因?yàn)闀邢嗤螖?shù)量的上坡以及下坡。

輸出格式

請輸出山頂位置由左而右非遞減的山稜線形狀總數(shù)。
由于答案可能很大，你只要輸出以十進(jìn)位表示時，它的最后9位數(shù)即可。

樣例

INPUT

6

OUTPUT

4

HINT

佔(zhàn)總分20%的測試數(shù)據(jù)中 n<=60

佔(zhàn)總分40%的測試數(shù)據(jù)中 n<=200

佔(zhàn)總分100%的測試數(shù)據(jù)中 n<=3000

SOLUTION

這題考場上耗了我大半的時間還沒搞出來qwq。

首先，根據(jù)題意分析，很容易就能看出這是個區(qū)間dp。

區(qū)間dp怎么傳遞呢？看到題目要求：求寬度為\(n\)，山頂高度非降的方案和。所以我們可以開一個二維數(shù)組\(dp[i][j]\)記錄答案：第一維\(i\)用來記錄限定條件：“寬度”；第二維\(j\)來記錄限定條件：這些山峰的最高高度\(j\)，以便轉(zhuǎn)移。

但是啊，我們的\(dp\)數(shù)組只能記錄最高高度為\(j\)的情況，那如果我要拓寬寬度的話，肯定是不能再把所有的最高高度的情況又重新枚舉累加的，所以考慮用一個前綴和數(shù)組\(sum[i][j]\)來記錄寬度為\(i\)，最高高度限定為\(j\)（可以小于\(j\)）的所有情況，可以說\(sum\)數(shù)組就是把寬度為\(i\)的所有合法情況記錄了下來。

接下來就是轉(zhuǎn)移了。

首先我們有兩大種情況：
Ⅰ.我們的\(dp[i][j]\)的情況可以直接由\(dp[i-1][j-1]\)的情況得到；
這就相當(dāng)于可以想象把\(dp[i-1][j-1]\)中包含的山的情況整體往上拱了一層。如下圖：

Ⅱ.我們也可以通過在\(sum[i-2][j]\)的基礎(chǔ)上加上一座最小的山。如下圖：

因?yàn)?span id="vt6mr5x" class="math inline">\(sum[i-2][j]\)加上一座單位高度的小山已經(jīng)把類似于最低山的高度大于單位長度的所有情況考慮了進(jìn)來，而我們的情況Ⅰ就是對應(yīng)著這種“最低山的高度大于單位長度”的所有情況。

所以任何情況已經(jīng)可以用以上兩種情況相互疊加著表示，可以保證的是這么算目前已經(jīng)沒有遺漏了。

但其實(shí)還會存在一個小問題。

在整體寬度為\(i+j\)時，假設(shè)我們的右邊有一座高度為\(j\)的山峰，那么顯然地，這座山峰的寬度為\(2j\)，所以去掉右邊的山峰后，我們左邊部分的山峰寬度為\(i-j\)，那么我們的\(sum[i-2j][j]\)就可以表示當(dāng)前說的這種情況的所有方案，此時是合法的。

不過我們?nèi)魧⒆筮叢糠值膶挾葴p少一個單位勻給右邊部分，右邊部分一定不能在保持只有一座山峰的情況下保證最高高度為\(j\)，所以不合法。

但是可能會有點(diǎn)想不通的是：為什么右邊就一定只能有一座山峰呢？

其實(shí)，注意一下我們的轉(zhuǎn)移方程，我們的\(sum[i-2][j]\)是通過和一個單位高度的山峰組合在一起作為答案加進(jìn)我們的\(dp\)數(shù)組里去的，然后當(dāng)我們的單位高度小山峰被墊高到了高度\(j\)時，與它同組搭配的\(sum\)數(shù)組的組合情況就必須考慮一下其合法性了，因?yàn)檫@種非法組合也本來就不能算在答案里。于是考慮刪除。

代碼就在下面，這篇題解其實(shí)更多就是對下面的代碼的解釋因?yàn)檫@個標(biāo)程一點(diǎn)注釋都沒有啊。

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> using namespace std; const int N=3010; const int P=1000000000; int n,dp[N][N],sum[N][N]; int main(){int i,j;memset(dp,0,sizeof(dp));memset(sum,0,sizeof(sum));dp[1][1]=1;sum[1][1]=1;for (i=2;i<=3000;++i){for (j=1;j<i;++j){if ((i+j)%2==0){dp[i][j]=(dp[i-1][j-1]+sum[i-2][j])%P;if (i-j-j>0) {dp[i][j]=(dp[i][j]-sum[i-j-j-1][j]+P)%P;}}sum[i][j]=(sum[i-1][j]+dp[i][j])%P;}dp[i][i]=1;sum[i][i]=1;}while (scanf("%d",&n)!=EOF){int ans=0;for (i=1;i<=n/2;++i) {ans=(ans+dp[n-i][i])%P;}printf("%d\n",ans);}return 0; }

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

總結(jié)

以上是生活随笔為你收集整理的CSAPC08台湾邀请赛_T1_skyline的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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