2011-08-26 22:41:20Morris
b177. 山景 Skyline
b177. 山景 Skyline
作法 : DP
我承認我是來亂的
/**********************************************************************************/
/* Problem: b177 "山景 Skyline" from CSAPC'08 Problem Setter: Tmt, Seanwu */
/* Language: C */
/* Result: AC (38ms, 17407KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-26 14:47:10 */
/**********************************************************************************/
#include<stdio.h>
#define limit 1500
#define Mod 1000000000
long long DP[1501][1501] = {}, Ans[1501] = {};
long long Sum[1501] = {};
main() {
int a, b, c, d;
DP[0][0] = 1;
for(a = 1; a <= limit; a++) {
for(b = 1; b <= a; b++) {
DP[a][b] = (DP[a-1][b-1] + Sum[b])%Mod;
Sum[b] = (Sum[b] - DP[a-b][b] + DP[a][b])%Mod;
Ans[a] = (Ans[a] + DP[a][b])%Mod;
}
}
int n;
while(scanf("%d", &n) == 1) {
n /= 2;
if(n >= 48)
printf("%09lld\n", Ans[n]);
else
printf("%lld\n", Ans[n]);
}
return 0;
}
內容 ： | 正體中文 (zh_TW) | 簡體中文 (zh_CN)
一座山的山稜線由許多片段的45度斜坡構成，每一個片段不是上坡就是下坡。
*
* * /\
* /\ /\/ \
/\/ \/ \
在我們眼前的所見的任何寬度為n個單位的山稜形狀，可以輕鬆地觀察到所有山頂的位置。
請問有多少種山稜線的形狀，使得所有山頂的位置由左而右非遞減呢？
所有的山稜線都必須完整，也就是說左右兩端都必須是高度為0的山腳，而且不能有任何山谷的位置隱沒在地平線底下。
*
* * /\
* /\ /\/ \
/\/ \/ \
在我們眼前的所見的任何寬度為n個單位的山稜形狀，可以輕鬆地觀察到所有山頂的位置。
請問有多少種山稜線的形狀，使得所有山頂的位置由左而右非遞減呢？
所有的山稜線都必須完整，也就是說左右兩端都必須是高度為0的山腳，而且不能有任何山谷的位置隱沒在地平線底下。
輸入說明
：
輸入僅包含一個數字n，n一定會是偶數，因為會有相同片段數量的上坡以及下坡。
輸出說明
：
請輸出山頂位置由左而右非遞減的山稜線形狀總數。
由於答案可能很大，你只要輸出以十進位表示時，它的最後9位數即可。
由於答案可能很大，你只要輸出以十進位表示時，它的最後9位數即可。
範例輸入 ：
6
範例輸出 ：
4
提示
：
佔總分20%的測試數據中 n<=60
佔總分40%的測試數據中 n<=200
佔總分100%的測試數據中 n<=3000
佔總分40%的測試數據中 n<=200
佔總分100%的測試數據中 n<=3000
出處
：
CSAPC'08 Problem Setter: Tmt, Seanwu
(管理：tmt514)
作法 : DP
我承認我是來亂的
/**********************************************************************************/
/* Problem: b177 "山景 Skyline" from CSAPC'08 Problem Setter: Tmt, Seanwu */
/* Language: C */
/* Result: AC (38ms, 17407KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-26 14:47:10 */
/**********************************************************************************/
#include<stdio.h>
#define limit 1500
#define Mod 1000000000
long long DP[1501][1501] = {}, Ans[1501] = {};
long long Sum[1501] = {};
main() {
int a, b, c, d;
DP[0][0] = 1;
for(a = 1; a <= limit; a++) {
for(b = 1; b <= a; b++) {
DP[a][b] = (DP[a-1][b-1] + Sum[b])%Mod;
Sum[b] = (Sum[b] - DP[a-b][b] + DP[a][b])%Mod;
Ans[a] = (Ans[a] + DP[a][b])%Mod;
}
}
int n;
while(scanf("%d", &n) == 1) {
n /= 2;
if(n >= 48)
printf("%09lld\n", Ans[n]);
else
printf("%lld\n", Ans[n]);
}
return 0;
}