Problem 10684 The jackpot，賭博

此題需要用到動態規畫。告知一連串的賭局輸贏金額，要你求出在任一段連續賭局中，能獲得的最多金幣，只需輸出金幣數值即可。

只需利用動態規劃將較佳數值往後推，推到陣列結束，在找出陣列內最大值即可。這裡也用到了輸入優化的方法。C 語言程式碼如下：

#define SIZE 10001

int money[SIZE], record[SIZE];

int getInt()  
{  
    char ch;  
    int n = 0, isNegative = 0;
    while(ch = getchar())  
        if(ch != ' ' && ch != '\n') break;
    if (ch == '-') isNegative = 1;
    else n = ch - 48;
    while( ch = getchar())   
    {  
        if(ch == ' ' || ch == '\n') break;  
        n = n * 10 + ch - 48;  
    }  
    if(isNegative) return -n;
    return n;  
}

主程式內 ....
while (n = getInt())
{
    for (i = 0; i < n; i ++)
        money[i] = 0, record[i] = 0;
    int max = 0;  
    money[0] = getInt();
    if (money[0] <= 0)
       record[0] = 0; 
    else 
       record[0] = money[0], max = money[0];
    for (i = 1; i < n; i ++)
    {
        money[i] = getInt();
        record[i] = money[i] < money[i] + record[i - 1] ? 
             money[i] + record[i - 1] : money[i];
        if (record[i] > max) max = record[i];
    }
    if (max == 0) puts("Losing streak.");
    else printf ("The maximum winning streak is %d.\n", max);
}

By David.K

p10684題目連結
回ACM題庫目錄
回首頁