列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[sagit]

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]

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

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]

其實這題是可以作到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;
}
}
}