http://www.elijahqi.win/2018/01/11/vijos1534-%e9%ab%98%e6%80%a7%e8%83%bd%e8%ae%a1%e7%ae%97%e6%9c%ba/
背景
WinterCamp 2001 高性能計算機(hpc)
Description:Official
Data:Official
Program:Unknown
描述
現在有一項時間緊迫的工程計算任務要交給你——國家高性能并行計算機的主管工程師——來完成。為了盡可能充分發揮并行計算機的優勢，我們的計算任務應當劃分成若幹個小的子任務。
這項大型計算任務包括A和B兩個互不相關的較小的計算任務。為了充分發揮并行計算機的運算能力，這些任務需要進行分解。研究發現，A和B都可以各自劃分成很多較小的子任務，所有的A類子任務的工作量都是一樣的，所有的B類子任務也是如此（A和B類的子任務的工作量不一定相同）。A和B兩個計算任務之間，以及各子任務之間都沒有執行順序上的要求。
這台超級計算機擁有p個計算節點，每個節點都包括一個串行處理器、本地主存和高速cache。然而由于常年使用和不連貫的更新，各個計算節點的計算能力并不對稱。一個節點的計算能力包括如下幾個方面：
1. 就本任務來說，每個節點都有三種工作狀态：待機、A類和B類。其中，A類狀态下執行A類任務；B類狀态下執行B類任務；待機狀态下不執行計算。所有的處理器在開始工作之前都處于待機狀态，而從其它的狀态轉入A或B的工作狀态（包括A和B之間互相轉換），都要花費一定的啟動時間。對于不同的處理節點，這個時間不一定相同。用兩個正整數
tiAt_i^A
tiA和
tiB (i=1,2,…,p)t_i^B~(i=1,2,…,p)
tiB (i=1,2,…,p)分别表示節點i轉入工作狀态A和工作狀态B的啟動時間（機關：ns）。
-
一個節點在連續處理同一類任務的時候，執行時間——不含狀态轉換的時間——随任務量（這一類子任務的數目）的平方增長，即：
若節點i連續處理x個A類子任務，則對應的執行時間為：
t=kiAx2t=k_i^Ax^2
t=kiAx2
類似的，若節點i連續處理x個B類子任務，對應的執行時間為：
t=kiBx2t=k_i^Bx^2
t=kiBx2
其中，
kiAk_i^A
kiA和
kiBk_i^B
kiB是系數，機關是ns，
i=1,2,…,pi=1,2,…,p
i=1,2,…,p。
任務配置設定必須在所有計算開始之前完成，所謂任務配置設定，即給每個計算節點設定一個任務隊列，隊列由一串A類和B類子任務組成。兩類子任務可以交錯排列。
計算開始後，各計算節點分别從各自的子任務隊列中順序讀取計算任務并執行，隊列中連續的同類子任務将由該計算節點一次性讀出，隊列中一串連續的同類子任務不能被分成兩部分執行。
現在需要你編寫程式，給這p個節點安排計算任務，使得這個工程計算任務能夠盡早完成。假定任務安排好後不再變動，而且所有的節點都同時開始運作，任務安排的目标是使最後結束計算的節點的完成時間盡可能早。
格式
輸入格式
第一行是對計算任務的描述，包括兩個正整數
nAn_A
nA和
nBn_B
nB，分别是A類和B類子任務的數目，兩個整數之間由一個空格隔開。
後面部分是對此計算機的描述：
第二行是一個整數p，即計算節點的數目。
随後連續的p行按順序分别描述各個節點的資訊，第i個節點由第i+2行描述，該行包括下述四個正整數（相鄰兩個整數之間有一個空格）：
tiA tiB kiA kiBt_i^A~t_i^B~k_i^A~k_i^B
tiA tiB kiA kiB
輸出格式
隻有一行，包含有一個正整數，即從各節點開始計算到任務完成所用的時間。
樣例1
樣例輸入1
5 5
3
15 10 6 4
70 100 7 2
30 70 1 6
Copy
樣例輸出1
93
Copy
限制
本題一共6個測試點，第1、2、3點10分，第4、5點20分，第6點30分。
由于題目沒給時限，本人視實際情況，定第1、2、3點時限1s，第4點時限2s，第5、6點時限3s。
提示
1≤nA≤60,1≤nB≤60 1 \le n_A \le 60, 1 \le n_B \le 60
1≤nA≤60,1≤nB≤60
1≤p≤20 1 \le p \le 20
1≤p≤20
1≤tA≤1000,1≤tB≤1000,1≤kA≤50,1≤kB≤50 1 \le t_A \le 1000, 1 \le t_B \le 1000, 1 \le k_A \le 50, 1 \le k_B \le 50
1≤tA≤1000,1≤tB≤1000,1≤kA≤50,1≤kB≤50
來源
WinterCamp 2001 高性能計算機(hpc)
Description:Official
Data:Official
Program:Unknown
自己菜菜的啊 觀摩icefox巨佬題解 可知 我們現在其實相當于分成了兩個子任務待解決 1、針對每個點節點計算出 t[0/1][i][j]表示 最後一個做的是A 還是B 然後我已經做了i個A j個B了的最小時間花費是多少 2、dp[now][i][j]表示 現在處于第now個節點 已經處理了i個A j個B真正的最小時間花費
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 66
using namespace std;
int t[2][N][N],dp[22][N][N],tim[22][N][N],na,nb,n,ta[N],tb[N],ka[N],kb[N];
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0;char ch=gc();
while(ch<'0'||ch>'9') ch=gc();
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();return x;
}
int main(){
freopen("vijos1534.in","r",stdin);
na=read();nb=read();n=read();
for (int i=1;i<=n;++i) ta[i]=read(),tb[i]=read(),ka[i]=read(),kb[i]=read();
for (int i=1;i<=n;++i){
memset(t,0x3f,sizeof(t));t[0][0][0]=t[1][0][0]=0;
for (int ii=0;ii<=na;++ii)
for (int j=0;j<=nb;++j){
for (int z=1;z<=ii;++z) t[0][ii][j]=min(t[0][ii][j],t[1][ii-z][j]+ta[i]+ka[i]*z*z);
for (int z=1;z<=j;++z) t[1][ii][j]=min(t[1][ii][j],t[0][ii][j-z]+tb[i]+kb[i]*z*z);
tim[i][ii][j]=min(t[0][ii][j],t[1][ii][j]);
}
}memset(dp,0x3f,sizeof(dp));
for (int i=0;i<=na;++i)
for (int j=0;j<=nb;++j) dp[1][i][j]=tim[1][i][j];
for (int now=2;now<=n;++now)
for (int i=0;i<=na;++i)
for (int j=0;j<=nb;++j)
for (int ki=0;ki<=i;++ki)
for (int kj=0;kj<=j;++kj)
dp[now][i][j]=min(dp[now][i][j],max(dp[now-1][i-ki][j-kj],tim[now][ki][kj]));
printf("%d",dp[n][na][nb]);
return 0;
}