動態規劃

由於奶牛每次擠奶後都要休息R小時，我們不妨把這R小時加到每個時間段的後面。每個時間段看成一個帶權區間，我們要求的是不重疊區間的權值和的最大值。

O(N^2)的算法

首先對每個區間按照左端的位置升冪排序，然後進行動態規劃。

狀態設定

* F[i]爲前i個區間，右端最大的區間爲i時，所得到的最大值 

狀態轉移方程

* F[i]=Max{ F[k] } + W[i] (k=1..i-1 並且 right[k] <= left[i])
      o W[i]爲區間i的價值
      o right[k]爲區間k的右端
      o left[i]爲區間i的左端 

邊界條件

* F[0]=0 

目標結果

* Ans=Max{ F[i] } (i=1..M) 

#include <iostream>
#define MAX 1001
using namespace std;

typedef struct
{
    int left,right,value;
}extent;

int T,N,R,Ans;
int F[MAX];
extent E[MAX];

inline int cmp(const void *a,const void *b)
{
    return ((extent *)a)->left - ((extent *)b)->left;
}

void init()
{
    int i;
    freopen("milkprod.in","r",stdin);
    freopen("milkprod.out","w",stdout);
    cin >> T >> N >> R;
    T+=R;
    for (i=1;i<=N;i++)
    {
        scanf("%d%d%d",&E[i].left,&E[i].right,&E[i].value);
        E[i].right+=R;
    }
    qsort(E+1,N,sizeof(E[0]),cmp);
}

void dynamic()
{
    int i,j,max;
    for (i=1;i<=N;i++)
    {
        max=0;
        for (j=1;j<=i-1;j++)
            if (E[j].right<=E[i].left && F[j]>max)
                max=F[j];
        F[i]=max+E[i].value;
        if (F[i]>Ans)
            Ans=F[i];
    }
}

int main()
{
    init();
    dynamic();
    cout << Ans << endl;
    return 0;
}

<a href="http://www.ruvtex.cn/wiki/USACOMonthly/2007_11_S/Milking_Time/Chinese">擠奶時間</a>

譯 By BYVoid

描述

貝茜是一隻非常努力工作的奶牛，她總是專注於提高自己的產量。爲了產更多的奶，她預計好了接下來的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