Yeefan's Blog: 2011-11-20

2011年11月26日星期六

通過“歸併排序”尋找逆序對

題目描述

给出一个整数数列A,输出这个数列中的逆序对数量
逆序对定义：
Ai<Aj 而且 i>j
输入格式
第一行一个整数n
下面有n行，每行一个正整数
输出格式
一个整数，逆序对数目
数据规模：
n=50000
数列中的数小于1000000

【分析】
雖然題目很簡單，但是數據量很大，所以直接暴力搜索肯定會超時。本題可以用歸併排序（Merge Sort）來快速完成。
【正確代碼】

C++语言: Codee#24223

//通過歸併排序尋找逆序對

#include <cstdio>

#include <cstdlib>

#include <iostream>

#define MAX 500005

int n,t[MAX],a[MAX];

long long sum;

void merge(int l, int mid, int r )

{

    int p = 0;

    int i = l, j = mid + 1;

    while(i <= mid&& j <= r)

    {

        if(a[i] > a[j])

        {

            t[p++] = a[j++];

            sum =sum + mid - i + 1;

        }

        else 

        {

            t[p++] = a[i++];

        }

    }

    while(i <= mid) t[p++] = a[i++];

    while(j <= r) t[p++] = a[j++];

    for(i = 0; i < p; i++)

    {

        a[l + i] = t[i];

    }

}

void mergesort(int l ,int r)

{

    if(l < r)

    {

        int mid = (r - l) / 2 + l;

        mergesort(l , mid);

        mergesort(mid + 1 , r);

        merge(l, mid , r);

    }

}

int main()

{

    freopen("px.in","r",stdin);

    freopen("px.out","w",stdout);

    scanf("%d\n",&n);

    sum=0;

    for(int i = 0; i < n; i++)

    {

        scanf(" %d ", &a[i]);

    }

    mergesort(0 , n - 1);

    printf("%lld\n", sum);

    return 0;

}

經典算法：歸併操作和歸併排序 merge & merge sort

歸併操作就是把兩個已經有序的數組合併為一個數組的過程。
廢話不多說了，直接上代碼。如果不會輕看維基百科。

C++语言: Codee#24222

//歸併操作（merge）

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;    

int A[1000],B[1000];

int C[2000];

int N;

void merge()  

{  

    int p=0;

    int i=1,j=1;

    while(i<=N&&j<=N)  

    {  

        if(A[i]<B[j])  

        {  

            C[++p]=A[i++];  

        }  

        else   

        {  

            C[++p]=B[j++];  

        }  

    }  

    while(i<=N) C[++p]=A[i++];  

    while(j<=N) C[++p]=B[j++];  

} 

int main()

{

    freopen("merge.in","r",stdin);

    freopen("merge.out","w",stdout);

    cin>>N;

    for (int i=1;i<=N;i++)

        cin>>A[i];

    for (int i=1;i<=N;i++)

        cin>>B[i];

    merge();

    for (int i=1;i<=2*N;i++)

        cout<<C[i]<<" ";

    return 0;

}

通過歸併操作，我們可以實現歸併排序（Merge Sort）。歸併排序是遞歸排序算法，使用了分治、二分的思想，把一個數組分為兩個部分，把這每個部分再分為兩個部分，就這樣一次一次的分下去，然後再把它們一次通過歸併操作合併起來，最後完成排序操作。

例題：通過歸併排序尋找逆序對

NOIP2011普及組複賽解題報告

pdf試題下載
1．數字反轉 reverse
【問題描述】

給定一個整數，請將該數各個位上數字反轉得到一個新數。新數也應滿足整數的常見形式，即除非給定的原數爲零，否則反轉後得到的新數的最高位數字不應爲零（參見樣例2）。

【輸入】

輸入文件名爲reverse.in。

輸入共1 行，一個整數N。

【輸出】

輸出文件名爲reverse.out。

輸出共1 行，一個整數，表示反轉後的新數。

【輸入輸出樣例1】

reverse.in

123

reverse.out

321

【輸入輸出樣例2】

reverse.in

-380

reverse.out

-83

【數據範圍】

-1,000,000,000 ≤ N≤ 1,000,000,000。

【分析】

普及組的水題，直接模擬即可。

注意：

1.讀入時用字符串讀入。

2.注意輸入“0”的情況。

【我的代碼】

C++语言: Codee#24218

//NOIP2011_Junior_reverse

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int main()

{

    freopen("reverse.in","r",stdin);

    freopen("reverse.out","w",stdout);

    char line[100]={'\0'};

    scanf("%s\n",&line);

    int s=0;

    int len=strlen(line);

    len--;

    if(line[0]=='0')

        printf("0\n");

    else

    {

        if(line[0]=='-')

        {

            s++;

            printf("-");

        }

        while(line[len--]=='0');

        for (int i=len+1;i>=s;i--)

            printf("%c",line[i]);

        printf("\n");

    }

    return 0;

}

【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	273 KB	0
2	正确	10	0.000 s	273 KB	0
3	正确	10	0.000 s	273 KB	0
4	正确	10	0.000 s	273 KB	0
5	正确	10	0.000 s	273 KB	0
6	正确	10	0.000 s	273 KB	0
7	正确	10	0.000 s	273 KB	0
8	正确	10	0.000 s	273 KB	0
9	正确	10	0.000 s	273 KB	0
10	正确	10	0.000 s	273 KB	0

运行完成
运行时间 0.003 s
平均内存使用 273 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

2.統計單詞數 stat
【問題描述】

一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統計出特定單詞在文章中出現的次數。

現在，請你編程實現這一功能，具體要求是：給定一個單詞，請你輸出它在給定的文章中出現的次數和第一次出現的位置。注意：匹配單詞時，不區分大小寫，但要求完全匹配，即給定單詞必須與文章中的某一獨立單詞在不區分大小寫的情況下完全相同（參見樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例2）。

【輸入】

輸入文件名爲stat.in，2 行。

第1 行爲一個字符串，其中只含字母，表示給定單詞；

第2 行爲一個字符串，其中只可能包含字母和空格，表示給定的文章。

【輸出】

輸出文件名爲stat.out。

只有一行，如果在文章中找到給定單詞則輸出兩個整數，兩個整數之間用一個空格隔開，分別是單詞在文章中出現的次數和第一次出現的位置（即在文章中第一次出現時，單詞首字母在文章中的位置，位置從0 開始）；如果單詞在文章中沒有出現，則直接輸出一個整數-1。

【輸入輸出樣例1】

stat.in

to be or not to be is a question

stat.out

2 0

【輸入輸出樣例1 說明】

輸出結果表示給定的單詞To 在文章中出現兩次，第一次出現的位置爲0。

【輸入輸出樣例2】

stat.in

Did the Ottoman Empire lose its power at that time

stat.out

-1

【輸入輸出樣例2 說明】

表示給定的單詞to 在文章中沒有出現，輸出整數-1。

【數據範圍】

1 ≤ 單詞長度≤ 10。

1 ≤ 文章長度≤ 1,000,000。

【分析】
這是NOIP2011複賽普及組中的第二道字符串處理題了～
讀入時都把大寫字母轉換成小寫，以方便判斷。
然後就很簡單了，直接暴力枚舉即可。
如果是string類，則之間用“=”號判等；如果是char型數組，用strcmp函數判等。

注意：
1.文章中空格有可能不止1個，要加以判斷。
2.只有strcmp函數返回0時才表示兩個字符數組相等。

【我的代碼】

C++语言: Codee#24217

//NOIP2011_Junior_stat

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

using namespace std;

int main()

{

    freopen("stat.in","r",stdin);

    freopen("stat.out","w",stdout);

    char str[11];

    memset(str,'\0',sizeof(str));

    int len;

    cin>>str;

    len=strlen(str);

    for (int i=0;i<len;i++)

        str[i]=tolower(str[i]);

    string art;

    char tmp[1000001]={'\0'};

    int pos=-1;

    int tot=0;

    int tl;

    getline(cin,art);

    getline(cin,art);

    tl=art.length();

    for (int i=0;i<tl;i++)

        tmp[i]=art[i];

    int i=0;

    while(i<tl)

    {

        if(isalpha(tmp[i]))

        {

            int j=i;

            int k=0;

            char arr[1001]={'\0'};

            while(isalpha(tmp[j]))

            {

                arr[k]=tolower(tmp[j]);

                k++;

                j++;

            }

            if(strcmp(str,arr)==0)

            {

                tot++;

                if(pos==-1)

                    pos=i;

            }

            i=j+1;

        }

        else

            i++;

    }

    if(tot!=0)

        cout<<tot<<" "<<pos<<endl;

    else

        cout<<-1<<endl;

    return 0;

}

【評測結果】
正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.001 s	1172 KB	0
2	正确	10	0.001 s	1172 KB	0
3	正确	10	0.001 s	1172 KB	0
4	正确	10	0.001 s	1168 KB	0
5	正确	10	0.003 s	1168 KB	0
6	正确	10	0.018 s	1176 KB	0
7	正确	10	0.018 s	1172 KB	0
8	正确	10	0.169 s	1172 KB	0
9	正确	10	0.167 s	1172 KB	0
10	正确	10	0.167 s	1176 KB	0

运行完成
运行时间 0.547 s
平均内存使用 1172 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

3.瑞士輪 swiss

【背景】

在雙人對決的競技性比賽，如乒乓球、羽毛球、國際象棋中，最常見的賽制是淘汰賽和循環賽。前者的特點是比賽場數少，每場都緊張刺激，但偶然性較高。後者的特點是較爲公平，偶然性較低，但比賽過程往往十分冗長。

本題中介紹的瑞士輪賽制，因最早使用於1895 年在瑞士舉辦的國際象棋比賽而得名。

它可以看作是淘汰賽與循環賽的折衷，既保證了比賽的穩定性，又能使賽程不至於過長。

【問題描述】

2*N 名編號爲1~2N 的選手共進行R 輪比賽。每輪比賽開始前，以及所有比賽結束後，都會按照總分從高到低對選手進行一次排名。選手的總分爲第一輪開始前的初始分數加上已參加過的所有比賽的得分和。總分相同的，約定編號較小的選手排名靠前。

每輪比賽的對陣安排與該輪比賽開始前的排名有關：第1 名和第2 名、第3 名和第4名、……、第2K – 1 名和第2K 名、…… 、第2N – 1 名和第2N 名，各進行一場比賽。每場比賽勝者得1 分，負者得0 分。也就是說除了首輪以外，其它輪比賽的安排均不能事先確定，而是要取決於選手在之前比賽中的表現。

現給定每個選手的初始分數及其實力值，試計算在R 輪比賽過後，排名第Q 的選手編號是多少。我們假設選手的實力值兩兩不同，且每場比賽中實力值較高的總能獲勝。

【輸入】

輸入文件名爲swiss.in。

輸入的第一行是三個正整數N、R、Q，每兩個數之間用一個空格隔開，表示有2*N 名選手、R 輪比賽，以及我們關心的名次Q。

第二行是2*N 個非負整數s1, s2, …, s2N，每兩個數之間用一個空格隔開，其中si 表示編號爲i 的選手的初始分數。

第三行是2*N 個正整數w1, w2, …, w2N，每兩個數之間用一個空格隔開，其中wi 表示編號爲i 的選手的實力值。

【輸出】

輸出文件名爲swiss.out。

輸出只有一行，包含一個整數，即R 輪比賽結束後，排名第Q 的選手的編號。

【輸入輸出樣例】

swiss.in

2 4 2

7 6 6 7

10 5 20 15

swiss.out

【輸入輸出樣例說明】

	本輪對陣	本輪結束後的得分
選手編號	/	①	②	③	④
初始	/	7	6	6	7
第1 輪	①—④ ②—③	7	6	7	8
第2 輪	④—① ③—②	7	6	8	9
第3 輪	④—③ ①—②	8	6	9	9
第4 輪	③—④ ①—②	9	6	10	9

【數據範圍】

對於30%的數據，1 ≤ N≤ 100；

對於50%的數據，1 ≤ N≤ 10,000；

對於100%的數據，1 ≤ N≤ 100,000，1 ≤ R≤ 50，1 ≤ Q≤ 2N，0 ≤ s1, s2, …, s2N ≤ 10^8，1 ≤ w1,

w2, …, w2N ≤ 10^8。

【分析】

這是普及組的一道難題。

首先，由於每輪比賽的次序都是由上一輪比賽完後的比分決定的，因此對於普及組的同學來說僅能使用模擬的方法來解決。容易想到的是每一輪模擬完以後快排一次，用這樣的方法，時間複雜度爲O(2Nlog2N*R),根據數據範圍可知這種思路僅能解決50%的數據。因此我們需要一種更有效的方式。

分析題意後可以發現，對於每一輪比賽過後，每一位選手都會有一種狀態，贏了或者輸了，而每一位選手比賽前都是有序的，那麼對於所有在該輪比賽中贏了或者是輸了的選手，都是有序的。即每輪比賽後，我們可以以O(N)的效率獲得勝負選手的有序隊列，對於兩組有序序列，容易想到將兩組數列歸併，歸併的效率爲O(N)，這樣，完成一輪比賽的效率從O(2Nlog2N*R)縮減至O(NR)，根據數據範圍，這樣的程序是能夠在1秒內出解的。

【我的代碼】

C++语言: Codee#24224

/*

*Problem:NOIP2011_Junior_Swiss 瑞士輪

*Author:Yee-fan Zhu

*School:Henan Experimental High School

*Method:Merge,QuickSort

*Date:2011.11.26

*/

#include <iostream>

#include <cstdio>

#include <cstdlib>

using namespace std;

class SWISS

{

public:

    int num;

    int val;

    int tot;

}P[200003];

int N,R,Q;

SWISS A[100001],B[100001];

int pa,pb;

int cmp(const void *a,const void *b)

{

    class SWISS *c=(class SWISS *)a;

    class SWISS *d=(class SWISS *)b;

    if(c->tot!=d->tot)

        return d->tot-c->tot;

    return c->num-d->num;

}

void init()

{

    scanf("%d %d %d\n",&N,&R,&Q);

    N*=2;

    for(int i=1;i<=N;i++)

    {    

        P[i].num=i;

        scanf("%d",&P[i].tot);

    }

    for(int i=1;i<=N;i++)

        scanf("%d",&P[i].val);

    qsort(P+1,N,sizeof(SWISS),cmp);

}

void merge() 

{ 

    int p=0;

    int i=1,j=1;

    while(i<=N/2&&j<=N/2) 

    { 

        if(A[i].tot>B[j].tot)

        { 

            P[++p]=A[i++]; 

            continue;

        } 

        if(A[i].tot==B[j].tot)

        { 

            if(A[i].num<B[j].num)

            {    

                P[++p]=A[i++]; 

                continue;

            }

            P[++p]=B[j++]; 

            continue;

        } 

        P[++p]=B[j++]; 

    } 

    while(i<=N/2) P[++p]=A[i++]; 

    while(j<=N/2) P[++p]=B[j++]; 

} 

void work()

{

    for (int i=1;i<=R;i++)

    {

        int j=1;

        pa=0,pb=0;

        while(j<N)

        {

            if(P[j].val>P[j+1].val)

                P[j].tot++,A[++pa]=P[j],B[++pb]=P[j+1];

            else

                P[j+1].tot++,A[++pa]=P[j+1],B[++pb]=P[j];

            j+=2;

        }

        merge();

    }

    qsort(P+1,N,sizeof(SWISS),cmp);

    printf("%d\n",P[Q].num);

}

int main()

{

    freopen("swiss.in","r",stdin);

    freopen("swiss.out","w",stdout);

    init();

    work();

    return 0;

}

【評測結果】
正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	4960 KB	0
2	正确	10	0.000 s	4960 KB	0
3	正确	10	0.001 s	4960 KB	0
4	正确	10	0.019 s	4960 KB	0
5	正确	10	0.047 s	4960 KB	0
6	正确	10	0.123 s	4960 KB	0
7	正确	10	0.254 s	4960 KB	0
8	正确	10	0.468 s	4960 KB	0
9	正确	10	0.543 s	4960 KB	0
10	正确	10	0.612 s	4960 KB	0

运行完成
运行时间 2.068 s
平均内存使用 4960 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!

[搜索]AHOI2009：飛行棋 fly 解題報告

Description

給出圓週上的若干個點，已知點與點之間的弧長，其值均爲正整數，並依圓周順序排列。

請找出這些點中有沒有可以圍成矩形的，並希望在最短時間內找出所有不重複矩形。

Input

第一行爲正整數N，表示點的個數，接下來N行分別爲這N個點所分割的各個圓弧長度

Output

所構成不重複矩形的個數

Sample Input

8 1 2 2 3 1 1 3 3

Sample Output

Hint

N<= 20

Source

HAOI2009-2 2009年安徽NOI省選第二試第一題

【分析】

省選中的水題，直接爆搜即可。

根據平面幾何的知識，構成矩形的充分條件是對邊相等。

由於數據量不大，深度優先搜索、廣度優先搜索均可，連開四層循環暴力枚舉都可以。

【我的代碼】
#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
int N;
int Q[5];
int S[21]={0};
int C[21];
int ans=0;

void init()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>C[i];
        S[i]=S[i-1]+C[i];
    }
}

void dfs(int deep,int num)
{
    if(deep==5)
    {
        if((S[N]-Q[2]-Q[3]-Q[4])==Q[3] && Q[2]==Q[4])
            ans++;
        return;
    }
    for (int i=num+1;i<=N;i++)
    {
        Q[deep]=S[i]-S[num];
        dfs(deep+1,i);
    }
}

int main()
{
    freopen("fly.in","r",stdin);
    freopen("fly.out","w",stdout);
    init();
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}

2011年11月25日星期五

[最短路]NOI1997：最優乘車 bustravel 解題報告

【描述】
H城是一個旅遊勝地，每年都有成千上萬的人前來觀光。爲方便遊客，巴士公司在各個旅遊景點及賓館，飯店等地都設置了巴士站並開通了一些單程巴上綫路。每條單程巴士綫路從某個巴士站出發，依次途經若干個巴士站，最終到達終點巴士站。

一名旅客最近到H城旅遊，他很想去S公園遊玩，但如果從他所在的飯店沒有一路巴士可以直接到達S公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺的另一路巴士, 這樣換乘幾次後到達S公園。

現在用整數1,2,…N 給H城的所有的巴士站編號，約定這名旅客所在飯店的巴士站編號爲1,S公園巴士站的編號爲N。

寫一個程序，幫助這名旅客尋找一個最優乘車方案,使他在從飯店乘車到S公園的過程中換車的次數最少。

輸入輸出

輸入文件的第一行有兩個數字M和N(1<=M<=100 1<N<=500)，表示開通了M條單程巴士綫路，總共有N個車站。從第二行到第M+1行依次給出了第1條到第M條巴士綫路的信息。其中第 i+1行給出的是第i條巴士綫路的信息，從左至右按運行順序依次給出了該綫路上的所有站號相鄰兩個站號之間用一個空格隔開。

輸出文件只有一行。如果無法乘巴士從飯店到達S公園，則輸出"N0"，否則輸出你的程序所找到的最少換車次數，換車次數爲0表示不需換車即可到達

樣例

輸入文件

3 7

6 7

4 7 3 6

2 1 3 5

輸出文件

【分析】

最短路徑問題，可以用Floyd算法求解。只是讀入時不太方便，需要先讀一整行。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAXN=10000000;
int Bus[101][501];
int Map[501][501];
int N,M;

void init()
{
    string line;
    scanf("%d %d\n",&M,&N);

    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            Map[i][j]=MAXN;

    for (int i=1;i<=M;i++)
    {
        Bus[i][0]=0;
        getline(cin,line);
        int tmp=0;
        int len=line.length();
        int top=0;
        while(top<len)
        {
            if(isdigit(line[top]))
            {
                tmp=tmp*10+line[top]-'0';
                top++;
                continue;
            }
            if(line[top]==' ')
            {
                Bus[i][0]++;
                Bus[i][Bus[i][0]]=tmp;
                tmp=0;
                top++;
                continue;
            }
        }
        if(tmp>0)
        {
            Bus[i][0]++;
            Bus[i][Bus[i][0]]=tmp;
        }
    }

    int t1,t2;
    for (int i=1;i<=M;i++)
    {
        for (int j=1;j<=Bus[i][0];j++)
        {
            for (int k=j;k<=Bus[i][0];k++)
            {
                t1=Bus[i][j];
                t2=Bus[i][k];
                Map[t1][t2]=0;
            }
        }
    }
}

void Floyd()
{
    int tmp;
    for (int k=1;k<=N;k++)
    {
        for (int i=1;i<=N;i++)
        {
            for (int j=1;j<=N;j++)
            {
                tmp=Map[i][k]+Map[k][j]+1;
                if(tmp<Map[i][j])
                    Map[i][j]=tmp;
            }
        }
    }
    printf("%d\n",Map[1][N]);
}

int main()
{
    freopen("bustravel.in","r",stdin);
    freopen("bustravel.out","w",stdout);
    init();
    Floyd();
    return 0;
}

【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	1452 KB	0
2	正确	10	0.000 s	1452 KB	0
3	正确	10	0.001 s	1452 KB	0
4	正确	10	0.000 s	1452 KB	0
5	正确	10	0.003 s	1452 KB	0
6	正确	10	0.003 s	1452 KB	0
7	正确	10	0.001 s	1452 KB	0
8	正确	10	0.003 s	1452 KB	0
9	正确	10	0.003 s	1452 KB	0
10	正确	10	0.308 s	1452 KB	0

运行完成
运行时间 0.325 s
平均内存使用 1452 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
已完成数据库校验。

[動態規劃]USACO Nov07 Silver :Milking Time 擠奶時間(milkprod) 解題報告

譯 By CmYkRgB123
描述

貝茜是一隻非常努力工作的奶牛，她總是專注於提高自己的產量。爲了產更多的奶，她預計好了接下來的N (1 ≤ N ≤ 1,000,000)個小時，標記爲0..N-1。

Farmer John 計劃好了 M (1 ≤ M ≤ 1,000) 個可以擠奶的時間段。每個時間段有一個開始時間(0 ≤ 開始時間 ≤ N), 和一個結束時間 (開始時間 < 結束時間 ≤ N), 和一個產量 (1 ≤ 產量 ≤ 1,000,000) 表示可以從貝茜擠奶的數量。Farmer John 從分別從開始時間擠奶，到結束時間爲止。每次擠奶必須使用整個時間段。

但即使是貝茜也有她的產量限制。每次擠奶以後，她必須休息 R (1 ≤ R ≤ N) 個小時才能下次擠奶。給定Farmer John 計劃的時間段，請你算出在 N 個小時內，最大的擠奶的量。

輸入

第 1 行: 三個整數 N, M, R
第 2..M+1 行: 第 i+1 行每行三個整數，爲每個時間段的開始時間、結束時間、產量

輸出

第 1 行:一個整數在 N 個小時內，最大的擠奶的量Farmer John放入擠奶計劃，開始時間，結束時間，產量。

樣例輸入

12 4 2

1 2 8

10 12 19

3 6 24

7 10 31

樣例輸出

【分析】

線性動態規劃。

由於題目中說每個擠奶時間段的結束時間都小於等於N，所以我們可以把每個擠奶時間段的結束時間加上R，可以在不影響結果的情況下為DP提供方便。

接著對擠奶時間段以每個時間段的開始時間為關鍵字進行快速排序。

狀態設定：

V[i]：排序後第i個區間的產量

S[i]：排序後第i個區間的開始時間

E[i]：排序後第i個區間的結束時間+R

F[i]：對於前i個時間段，在結束時間小於第i個時間段的結束時間(即E[i])時所獲得的最大擠奶產量。

邊界條件：

F[0]=0

狀態轉移方程：

F[i]=max{F[j]}+V[i] (1≤j≤i-1，E[j]≤S[i])

目標結果：

F[i]=max{F[i]}

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class MILK
{
public:
    int S;
    int E;
    int V;
}P[1001];
int F[1001];
int N,M,R;

int cmp(const void *a,const void *b)
{
    class MILK *c=(class MILK *)a;
    class MILK *d=(class MILK *)b;
    return c->S-d->S;
}

int Max(int a,int b)
{
    if(b>a)
        a=b;
    return a;
}

void init()
{
    scanf("%d %d %d\n",&N,&M,&R);
    for (int i=1;i<=M;i++)
    {
        scanf("%d %d %d\n",&P[i].S,&P[i].E,&P[i].V);
        P[i].E+=R;
    }
    qsort(P+1,M,sizeof(MILK),cmp);
}

void dynamic()
{
    F[0]=0;
    int Maxn=0;
    for (int i=1;i<=M;i++)
    {
        Maxn=0;
        for (int j=1;j<=i-1;j++)
        {
            if(P[j].E<=P[i].S)
            {
                Maxn=Max(Maxn,F[j]);
            }
        }
        Maxn+=P[i].V;
        F[i]=Maxn;
    }

    Maxn=0;
    for (int i=1;i<=M;i++)
    {
        Maxn=Max(Maxn,F[i]);
    }
    printf("%d\n",Maxn);
}

int main()
{
    freopen("milkprod.in","r",stdin);
    freopen("milkprod.out","w",stdout);
    init();
    dynamic();
    return 0;
}

訂閱：文章 (Atom)

申請SAE

2011年11月26日 星期六

通過“歸併排序”尋找逆序對

經典算法：歸併操作 和 歸併排序 merge & merge sort

NOIP2011普及組 複賽 解題報告

[搜索]AHOI2009：飛行棋 fly 解題報告

2011年11月25日 星期五

[最短路]NOI1997：最優乘車 bustravel 解題報告

[動態規劃]USACO Nov07 Silver :Milking Time 擠奶時間(milkprod) 解題報告

2011年11月26日星期六

經典算法：歸併操作和歸併排序 merge & merge sort

NOIP2011普及組複賽解題報告

2011年11月25日星期五