2011-09-04 19:55:30Morris
d042. 11420 - Chest of Drawers
d042. 11420 - Chest of Drawers
內容 ：
斗櫃就是如左圖由很多抽屜垂直排列組成的櫃子。雖然這是個很有用的家具，但是如果要鎖這些抽屜時卻發生了問題——抽屜即使上鎖了也不一定安全。例如假設從上面往下數第三個抽屜鎖上了，但是它上面的那個抽屜卻沒鎖。這時鎖起來的抽屜也不安全，因為只要把它上面的抽屜整個拉出來就可拿到裡面的東西了。
一個 n 個抽屜的斗櫃，會有數個方式來確保剛好有 s 個抽屜是安全的。以左圖的斗櫃為例，有六個方式可以確保剛好四個抽屜是安全的。這六個方式如圖 2 所示。
給你 n 和 s 的值，請你算有多少個方式可以確保它們的安全。
圖 2: 圖中的 L 表示那個抽屜是鎖著的，U 則表示沒上鎖。這就是可以確保剛好 4 個抽屜是安全的的六個組合。安全的抽屜以粗體字母來表示。 |
輸入說明
：
輸入檔最多有 5000 行的輸入。
每行有兩個整數 n 及 s (1 ≤ n ≤ 65 且 0 ≤ s ≤ 65)。其中 n 是共有幾個抽屜，s 是要確保安全的抽屜數量。
輸入以含有兩個負數的一行作為結束。請不要處理這行輸入。
輸出說明
：
相對於每行的輸入要產生一行輸出。這行要含有一個表示有幾個方法可以確保 n 個抽屜中剛好有 s 個抽屜是安全的。
範例輸入 ：
6 2 6 3 6 4 -1 -1
範例輸出 ：
16 9 6
提示
：
DP
出處
：
/**********************************************************************************/
/* Problem: d042 "11420 - Chest of Drawers" from UVa ACM 11420 */
/* Language: C */
/* Result: AC (0ms, 302KB) on ZeroJudge */
/* Author: morris1028 at 2011-09-04 19:42:59 */
/**********************************************************************************/
#include<stdio.h>
main() {
int n, s, i, j;
long long DP[70][70][2] = {};/*[total][safe][U(0) or L(1)]*/
DP[1][1][1] = 1, DP[1][0][0] = 1;
for(i = 1; i <= 64; i++) {
for(j = 0; j <= i; j++) {
DP[i+1][j+1][1] += DP[i][j][1];/*LL*/
DP[i+1][j][0] += DP[i][j][0] + DP[i][j][1];/*UU LU*/
DP[i+1][j][1] += DP[i][j][0];/*UL*/
}
}
while(scanf("%d %d", &n, &s) == 2) {
if(n < 0 && s < 0) break;
printf("%lld\n", DP[n][s][0] + DP[n][s][1]);
}
return 0;
}
每次看到DP題，都沒辦法自己想出來，
Google後，常常看到別人的解才恍然大悟，
也自己憑空再想一遍，但是下次遇到類似的，
還是沒辦法應用，真傷腦筋，不曉得台長你有什麼建議?
同一題的 DP 可能會有好幾種不同的寫法，直不直觀因人而異，也沒有強迫全部人的方式都相同，沒有必要侷限在相同的式子上，說不定能想到更簡潔的思路。
對於無法應用上，這一點經常會發生的，「啊！怎麼會沒想到」明明知道卻一時想不到，就算想到也不見得在時間內 AC。這一點經驗補足吧，我也不是國手那類的人，學道理就能精通，對於道理的掌握不夠準確，套用哪一類型的，還是將所有可能的技巧列出來，try 看看能不能將答案找到，try 的速度越快，可能看起來就很自然而然地好像很熟一樣。
那要怎麼紀錄類似的 DP 方法呢？通常是靠特別的題目來定位的，通常看到一種解法會想到是類似哪一題，而不是類似「書上的哪一種作法」個人覺得拿書本章節定位很難記住，解題的心路歷程更容易刻印。 2014-08-05 09:14:29