[動態規劃]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

樣例輸出

43

【分析】

線性動態規劃。

由於題目中說每個擠奶時間段的結束時間都小於等於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;
}