b090. D. 正直DE
http://zerojudge.tw/ShowProblem?problemid=b090
內容 ：
日本的貴族學校「Agnes」要來台開設分校了！
這間在日本以優秀研究成果享譽國際的大學，五年前在Agnes學園校長DE（學園高層充滿著不為人知的機密，故校長的名稱用神秘的代號DE稱之）熟嫻的外交手段經營下，向業界招募了五年五千億的大筆資金，並在極短的時間內超英趕美，登上全世界大學的TOP10。
在經過多年考核後，董事會決定在台灣設立國外第一所分校，台大校長在聽聞此消息後，準備從今年高中生中挑出間諜，潛入該學校收集情報，而你就是那位被挑中的天才高中生。
為了確保你可以通過「Agnes」的入學考試（雖然你是台灣最天才的高中生，但是要面對世界各地的高中生仍是一件不容易的事情！），台大派出校園內馬尾綁最好的學妹向「Agnes」的教學長蜜蜂騙取得了入學考試的題目（沒想到教學長喜歡馬尾女孩的傳聞是真的！）。
在看過入學考試的題目後，你對於拿滿分非常有自信，但為了降低間諜任務失敗的機率（任務失敗你就…嘿嘿嘿…），你決定在考前事先研究出計算該題目最快的方法（因為答案實在太難記了）。
以下便是「Agnes」的入學考試題目：
| 2007年Agnes學園入學考考題 試題卷共1頁，1題，滿分100分
第一題： (共 100%) ①定義二元數學運算子∮（A,B）=C，（此符號稱為tera operator） A,B,C各為一矩陣，其中 ②定義二元數學運算子
請按照背面的數值，計算每小題A1∮A2∮A3…∮AN-1∮AN 之結果。 （請翻頁繼續作答） |
聰明的你很快就發現了幾件重要的事實：
1. A矩陣的Column數目一定要等於B矩陣的Row數目才可以做∮運算。
2. C矩陣的大小一定會是Row(A)*Column(B)，也就是Row(C)=Row(A)且Column(C)=Column(B)。
3. 彼彼運算需要大量的計算時間，計算一次C=∮（A,B）需要
Row(A)* Column(A)*Column(B) 個彼彼運算。
4. 要計算超過2個以上的tera operation時，依照不同的順序會需要不同的彼彼運算次數。
例如：要計算A∮B∮C的話，有兩種選擇：
（(A∮B) ∮C） 或者 (A∮(B∮C))。
假設A是7x10的矩陣，B是10x22的矩陣，C是22x37的矩陣，則
(A∮B) ∮C需要(7*10*22) + (7*22*37) = 7238次彼彼運算
A∮(B∮C) 需要(10*22*37)+(7*10*37) = 10730次彼彼運算
5. 雖然利用其它的特殊技巧可以更快速的計算出答案，但為了防止自己算錯，你決定只利用添加括號的方式來加快運算速度（也就是改變運算的順序）。
根據你不平凡的智力，計算500次彼彼運算需要一張A4白紙，因此一張雙面A4總共可計算1000次，因為此次入學考試由正直的DE親自監考，正直的DE常常懷疑學生不正直，故你最好事先計算出最低所需的計算紙數量，以免當天考試因為帶太多計算紙而被正直的DE懷疑你的身份！
輸入說明
：
輸入檔以一個數字T為開頭，代表題目卷共有T個小題（1<=T<=5）。
每個小題以一個整數N（1<=N<= 1000），代表有幾個矩陣需要做運算，接著有N行輸入，Ri和Ci分別代表矩陣Ai的Row及Column大小（1<=Ri<=1000， 1<=Ci<=1000，1<=i<=N）。
輸出說明
：
對每一組小題，你應該輸出一個非負整數H，代表若單獨計算該小題最少需要幾張計算紙，且在最後一行輸出整場考試最少需使用幾張計算紙。
範例輸入 ：
2 3 7 10 10 22 22 37 6 30 35 35 15 15 5 5 10 10 20 20 25
範例輸出 ：
8 16 23
提示
：
出處
：
作法 : DP (矩陣乘積鏈最小次數)
/**********************************************************************************/
/* Problem: b090 "D. 正直DE" from 2007 NPSC 高中組決賽 */
/* Language: C */
/* Result: AC (4396ms, 6392KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-17 16:25:11 */
/**********************************************************************************/
#include<stdio.h>
long long DP[1002][1002] = {}, A[1002];
long long MAX = 0x7fffffffffffffffLL, temp, m;
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n' || cha == EOF) break;
if(cha == EOF) return -1;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
main() {
int n, t, a, b, c, d;
long long total = 0, Ans;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(a = 0; a < n; a++)
A[a] = Input(), A[a+1] = Input();
DP[a][a] = 0;
for(a = 1; a < n; a++) {
for(b= 0, c= a + b; c < n; b++, c++) {
m = MAX;
for(d = b; d < c; d++) {
temp = DP[b][d] + DP[d+1][c] + A[b]*A[d+1]*A[c+1];
if(m > temp) m = temp;
}
DP[b][c] = m;
}
}
Ans = DP[0][n-1];
printf("%lld\n", (Ans-1)/1000+1);
total += Ans;
}
printf("%lld\n", (total-1)/1000+1);
return 0;
}