題目描述

某加工廠有A、B兩臺機(jī)器，來加工的產(chǎn)品可以由其中任何一臺機(jī)器完成，或者兩臺機(jī)器共同完成。由于受到機(jī)器性能和產(chǎn)品特性的限制，不同的機(jī)器加工同一產(chǎn)品所需的時間會不同，若同時由兩臺機(jī)器共同進(jìn)行加工，所完成任務(wù)又會不同。某一天，加工廠接到n個產(chǎn)品加工的任務(wù)，每個任務(wù)的工作量不盡一樣。
你的任務(wù)就是：已知每個任務(wù)在A機(jī)器上加工所需的時間t1, B機(jī)器上加工所需的時間t2及由兩臺機(jī)器共同加工所需的時間t3，請你合理安排任務(wù)的調(diào)度順序，使完成所有n個任務(wù)的總時間最少。

輸入輸出格式

輸入格式
（輸入文件共n+1行）
第1行為 n。 n是任務(wù)總數(shù)（1≤n≤6000）
第i+1行為3個[0，5]之間的非負(fù)整數(shù)t1,t2,t3，分別表示第i個任務(wù)在A機(jī)器上加工、B機(jī)器上加工、兩臺機(jī)器共同加工所需要的時間。如果所給的時間t1或t2為0表示任務(wù)不能在該臺機(jī)器上加工，如果t3為0表示任務(wù)不能同時由兩臺機(jī)器加工。

輸出格式
最少完成時間

輸入輸出樣例

輸入樣例#1

5
2 1 0
0 5 0
2 4 1
0 0 3
2 1 1

輸出樣例#1

9

解題思路

終于有一道狀態(tài)轉(zhuǎn)移方程面積不那么龐大的DP題了（手動滑稽_ hua|ji_）
很顯然，如果我們分別考慮某個任務(wù)由第一個機(jī)器或者由第二個機(jī)器來完成的話，不管是時間復(fù)雜度還是空間復(fù)雜度都輸無法承受的，那么我們來考慮壓維
我們定義狀態(tài)變量 f [ i ] 表示第一個機(jī)器工作了 i 分鐘時第二個機(jī)器的工作時間，外層循環(huán)就是從 1 到 n ，也就是循環(huán)任務(wù)數(shù)量，當(dāng)我們每枚舉到一個任務(wù)時，先考慮它是否能夠被安排給第二個機(jī)器，如果可以，我們就把 f [ i ] 加上當(dāng)前的 t2 ，如果不行，就還把他設(shè)為一個極大值；然后我們再來考慮把它分給兩個機(jī)器或是兩個機(jī)器共同完成的最優(yōu)解，如果可以被分配給第一個機(jī)器時，第二個機(jī)器的時間就不用增加，轉(zhuǎn)移方程即為：

f [ i ] = min ( f [ i ] , f [ i - t1 ] ) ;

如果他能被分配給兩個機(jī)器共同完成時，不僅第一個機(jī)器的時間要轉(zhuǎn)移，第二個機(jī)器的時間也要增加，故轉(zhuǎn)移方程為：

f [ i ] = min ( f [ i ] , f [ i - t3 ] + t3 ) ;

需要注意的細(xì)節(jié)是，每次進(jìn)行轉(zhuǎn)移的時候內(nèi)層循環(huán)應(yīng)循環(huán)完成任務(wù)的總時間，又因?yàn)槲覀儔旱袅搜h(huán)物品的那一維，所以內(nèi)層循環(huán)應(yīng)從總時間循環(huán)到零，在這里我們可以進(jìn)行一個優(yōu)化，就是在讀入的時候邊讀邊進(jìn)行狀態(tài)轉(zhuǎn)移，定義一個 sum 變量每次加上讀入的 t1 , t2 , t3 中的最大值，循環(huán)結(jié)束時的 sum 即為完成任務(wù)的總時間
然后是最終答案，我們定義一個 ans ，初始化成極大值，然后循環(huán)總時間，每次取 min ( ans , max ( i , f [ i ] ) ) 即為最終答案
至于為什么是 max ( i , f [ i ] ) ，因?yàn)?i 表示第一個機(jī)器的時間，f [ i ]為第二個機(jī)器的時間，如果你只取較小的那個時間，則另一個機(jī)器很顯然還沒有完成任務(wù)，就不是滿足條件的答案，只有你取了兩個時間中的最大值才能保證兩個機(jī)器都完成了任務(wù)
下面是C++代碼，具體細(xì)節(jié)看注釋

C++代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rr register
using namespace std;

const int maxn=3e4+10;
const int inf=2147482647;
int n,t1,t2,t3,sum=0,ans=inf;
int f[maxn];

inline int read(){//珂朵莉版快讀~~~
    int chtholly=0,willem=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')willem=-1;c=getchar();}
    while(c<='9' && c>='0'){chtholly=chtholly*10+(int)(c-'0');c=getchar();}
    return chtholly*willem;
}

int main(){
    memset(f,127/3,sizeof(f));
    f[0]=0;//初始化f
    n=read();for(rr int i=1;i<=n;i++){
        t1=read(),t2=read(),t3=read();
        sum+=max(t1,max(t2,t3));
        for(rr int j=sum;j>=0;j--){
            if(t2)f[j]+=t2;else f[j]=inf;
            if(t1 && j>=t1)f[j]=min(f[j],f[j-t1]);
            if(t3 && j>=t3)f[j]=min(f[j],f[j-t3]+t3);
        }
    }
    for(rr int i=0;i<=sum;i++)ans=min(ans,max(i,f[i]));
    printf("%d\n",ans);
    return 0;
}