Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

跨年夜你去了正妹小璇的家跨年(注意：只有跨年)
為了增加一點浪漫情調

你想讓燈泡開開關關的，以為這樣感覺會很有feel

但是燈泡連續暗太久小璇會感到害怕並且從此不理你

小璇能忍受燈泡連續n單位的時間是暗的，而總時間是m單位時間。

你想寫一個程式，給定n和m的值，算出有幾種不同的明暗排列方式，每一種排列方式之中都不會出現暗超過連續 n單位時間的區段。

有兩個數字n和m以一個空白分開，其中 1<=n<=15，1<=m<=90。

2 4

13

範例輸出說明：

亮用○表示，暗用●表示，則有下面13種方式。

　１　○○○○　　　　２　●○○○　　　　３　●○●●
　４　●●○●　　　　５　○○○●　　　　６　○○●●
　７　○●○●　　　　８　○●●○　　　　９　●○○●
１０　●○●○　　　１１　●●○○　　　１２　○○●○
１３　○●○○

以下是不合題目敘述的方式。

　１　●●●●　　　　２　○●●●　　　　３　●●●○

TIOJ (管理：david942j)

作法 : DP
我不會導公式，所以別 ... 請你提供
DP[m][n][p] m : 總共m個燈泡， n : 連續暗的最大剛好n個， p : 在結尾有連續 p 個是暗的
定義 :
[1][0][0] = 1, [1][1][1] = 1;
1 . n = 0, p =0 : DP[m][0][0] = 1; (基本的)
2.  p = 0 : DP[m][n][0] = DP[m-1][n][0~n] (在結尾補亮的)
3.  n = p : DP[m][n][n] = DP[m-1][0~m][n-1](在結尾補暗的)
4.  p = 1 : DP[m][n][1] = DP[m-1][n][0](在結尾補暗的)
5.  others : DP[m][n][p] = DP[m-1][n][p-1](在結尾補暗的)

Ans = DP[m][0~n][0~n]

/**********************************************************************************/
/*  Problem: d624 "燈泡問題" from TIOJ                                        */
/*  Language: C                                                                   */
/*  Result: AC (4ms, 1306KB) on ZeroJudge                                         */
/*  Author: morris1028 at 2011-06-01 21:39:50                                     */
/**********************************************************************************/


#include<stdio.h>
main() {
    int n, m, p, a, b;
    long long DP[91][91][16] = {};
    DP[1][0][0] = 1, DP[1][1][1] = 1;
    for(m = 2; m <= 90; m++)
        for(n = 0; n <= m; n++)
            for(p = 0; p <= 15 && p <= n; p++) {
                if(n == 0 && p == 0)
                    DP[m][0][0] = 1;
                else if(p == 0) {
                    for(a = 0; a <= n && a <= 15; a++)
                        DP[m][n][0] += DP[m-1][n][a];
                }
                else if(n == p) {
                    for(a = 0; a <= n; a++)
                        DP[m][n][n] += DP[m-1][a][n-1];
                }
                else if(p == 1)
                    DP[m][n][1] = DP[m-1][n][0];
                else
                    DP[m][n][p] = DP[m-1][n][p-1];
        }
    while(scanf("%d %d", &n, &m) == 2) {
        long long Ans = 0;
        for(a = 0; a <= n; a++)
            for(b = 0; b <= n; b++)
                Ans += DP[m][a][b];
        printf("%lld\n", Ans);
    }
    return 0;
}