NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 G.獎金

作者 主題: NPSC 2008 高中組 決賽 G.獎金  (閱讀 2008 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
NPSC 2008 高中組 決賽 G.獎金
« 於: 十一月 30, 2009, 01:35:48 pm »

NPSC 2008 高中組 決賽 G.獎金

說明:給你一連串的數字,請你找出(一)某段連續數字減去1000後,加起來的總合是最大的。(二)某段連續數字減去1000後,加起來的總合再除以數字個數是最大的。

解法:動態規劃(DP)與直解的題目,方案二即是所有數字中最大的那個,而方案一則是最大連續元素和的題目,可以參考「DJWS的網路日誌」 http://www.csie.ntnu.edu.tw/~u91029/MaximumSubarray.html 的說明。我們用 S[n] 記錄以第 n 個數為最後一個數的最大連續元素和,則如果 S[n-1] <=0 ,則 S [n] 為第 n 個數字的值A[n];如果 S[n-1] >0 ,則我們將第 n 個元素也加進去,也就是 S[n]=S[n-1]+A[n]。因為我們只會使用到 S[] 的前一個元素,所以不需要使用一個陣列,只要用一個變數來記錄即可。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2008 高中組決賽
// 題目 G - 獎金
// By sagit at TCGS
#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    freopen("pg.in", "rt", stdin);
    freopen("pg.out", "w+t", stdout);
    ios_base::sync_with_stdio(false);
    int n, best1, best2, sum, a, i;
    while (1)
    {
        cin >> n;
        if (n==0) break;
        best1=best2=sum=0;
        for (i=0; i<n; i++)
        {
            cin >> a;
            a-=1000;
            if (a>best2) best2=a;       // 方案二是單日最大值
            if (sum<=0) sum=a;
            else sum+=a;
            if (sum>best1) best1=sum;   // 方案一是最大連續整數和
        }
        cout << best1 << " " << best2 << endl;
    }
//    system("PAUSE");
    return 0;
}
« 上次編輯: 十一月 30, 2009, 01:54:45 pm 由 sagit »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 G.獎金