NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2006高中組決賽
 NPSC 2006 高中組 決賽 C.畢業演奏

作者 主題: NPSC 2006 高中組 決賽 C.畢業演奏  (閱讀 2424 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 217
    • 檢視個人資料
NPSC 2006 高中組 決賽 C.畢業演奏
« 於: 十二月 04, 2009, 10:38:14 am »

NPSC 2006 高中組 決賽 C.畢業演奏

說明:給你 N 個人的開始日期、結束日期以及所需天數,一天只能選擇一個人的情況下,請問你最多可以滿足多少人?

解法:使用動態規劃(DP),使用一個陣列記錄到該天時,可以滿足的最大人數。然後一個一個人去試,如果某人所需天數為 P,而 P 天前的最大人數加一大於這一天的最大人數,則把這一天的最大人數設成 P 天前的最大人數加一,也就是 Match[j-p]+1。而為了避免重複計算,故將這個人的與之前的記錄分開,等計算完成後再合併回去。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2006 決賽 - 題目 C - 畢業演奏 //
#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

const int MAX=10000001;
short int Match[MAX], Now[MAX];

int main()
{
    ifstream fin("pc.in");
    ofstream fout("pc.out");
    int num, top, max, r, d, p, i, j;

    while (1)
    {
        fin >> num;
        if ( num==0 || fin.fail() ) break;
        Match[0]=0;
        for (i=0, top=0, max=0; i<num; i++)
        {
            fin >> r >> d >> p;
            if ( d > top )
            {
                for (j=top+1; j<=d; j++)
                    Match[j]=max;
                top=d;
            }
            for (j=r+p-1; j<=d; j++)
            {
                if ( Match[j-p]+1 > Match[j] )
                {
                    Now[j]=Match[j-p]+1;
                    if ( Now[j] > max ) max=Now[j];
                }
                else Now[j]=Match[j];
            }
            for (j=r+p-1; j<=d; j++)
                Match[j]=Now[j];
        }
        fout << max << endl;
    }

//    system("PAUSE");
    return 0;
}
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: NPSC 2006 高中組 決賽 C.畢業演奏
« 回覆 #1 於: 一月 04, 2011, 08:40:46 pm »

其實如果要避免重複計算
只要倒著做就可以了 . . (跟背包一樣 .)

for (j=r+p-1; j<=d; j++)

for (j=d; j>=r+p-1; j--)

所以陣列開一個就好 .


不過有點感覺怪怪的 . .
如果是1000筆 "1 10000000 1"

1000*1000W=100E


代碼: [選擇]
#include <iostream>

using namespace std;

short a[10000001];
int main(){
    int i, j, n, r, d, p, maxd;
    while( scanf("%d", &n)==1 && n>0 )
    {
        a[0]=0; maxd=0;
        for( i=0; i<n; i++ )
        {
            scanf("%d%d%d", &r, &d, &p);
            if( d>maxd )
            {
                for( j=maxd+1; j<=d; j++ )
                    a[j]=a[maxd];
                maxd=d;
            }
            for( j=d; j>=r+p-1; j-- )
                if( a[j-p]+1>a[j] )
                    a[j]=a[j-p]+1;
        }
        printf("%d\n", a[maxd]);
    }
    return 0;
}
記錄

phat

  • 新手
  • *
  • 文章數: 18
    • 檢視個人資料
回覆: NPSC 2006 高中組 決賽 C.畢業演奏
« 回覆 #2 於: 七月 12, 2011, 10:38:07 pm »

其實這題是可以作到O(N^2)的。


要先有一個概念:如果最後有合奏的學姐序列依照合奏時間用S1~Sk表示。

那麼對任意i,一定有Si的編號 < S(i+1)的編號。

也就是不會有a區間比b區間前面 但是a學姐比b學姐晚合奏完的情況。

 

怎麼證明呢?假設最佳序列是S'1~S'k而且其中存在一個i,S'i的編號 > S'(i+1)的編號

但經過一點點的小證明可以發現,把這兩個學姐交換順序也一定存在一個合法的合奏方案。

//因為區間有非嚴格遞增性才會合理。

 

所以我們可以用DP[j]表示做完前i個學姐,取了j個學姐時最右界的位置。

每個轉移O(1),總複雜度O(N^2)


代碼: [選擇]
#include <cstdio>
#define INF 1000100
int dp[1010], N, D, R, P, dm;

inline int fmax(int a, int b) {return a>b?a:b;}

int main() {
while(~scanf("%d", &N) && N) {
for(int i=1; i<=N; i++) dp[i] = INF;
for(int i=0; i<N; i++) {
scanf("%d%d%d", &D, &R, &P);
for(int j=i; j>=0; j--) {
dm = fmax(D, dp[j]+1);
if(dm+P-1 <= R && dp[j+1] > dm+P-1)
dp[j+1] = dm+P-1;
}
}
for(int i=N; i>=0; i--)
if(dp[i] != INF) {
printf("%d\n", i);
break;
}
}
}
« 上次編輯: 七月 12, 2011, 10:42:56 pm 由 phat »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2006高中組決賽
 NPSC 2006 高中組 決賽 C.畢業演奏