24h購物| | PChome| 登入
2011-06-18 07:39:22| 人氣974| 回應0 | 上一篇 | 下一篇

b090. D. 正直DE

推薦 0 收藏 0 轉貼0 訂閱站台

http://zerojudge.tw/ShowProblem?problemid=b090

內容 :

日本的貴族學校「Agnes」要來台開設分校了!

這間在日本以優秀研究成果享譽國際的大學,五年前在Agnes學園校長DE(學園高層充滿著不為人知的機密,故校長的名稱用神秘的代號DE稱之)熟嫻的外交手段經營下,向業界招募了五年五千億的大筆資金,並在極短的時間內超英趕美,登上全世界大學的TOP10

在經過多年考核後,董事會決定在台灣設立國外第一所分校,台大校長在聽聞此消息後,準備從今年高中生中挑出間諜,潛入該學校收集情報,而你就是那位被挑中的天才高中生。

為了確保你可以通過「Agnes」的入學考試(雖然你是台灣最天才的高中生,但是要面對世界各地的高中生仍是一件不容易的事情!),台大派出校園內馬尾綁最好的學妹向「Agnes」的教學長蜜蜂騙取得了入學考試的題目(沒想到教學長喜歡馬尾女孩的傳聞是真的!)。

在看過入學考試的題目後,你對於拿滿分非常有自信,但為了降低間諜任務失敗的機率(任務失敗你就…嘿嘿嘿…),你決定在考前事先研究出計算該題目最快的方法(因為答案實在太難記了)。

 

以下便是「Agnes」的入學考試題目:

2007Agnes學園入學考考題

試題卷共1頁,1題,滿分100

 

第一題: (共 100%)

定義二元數學運算子∮(A,B=C,(此符號稱為tera operator

A,B,C各為一矩陣,其中

定義二元數學運算子(此符號稱為彼彼運算子),其中X,Y各為一非負實數。

 

請按照背面的數值,計算每小題A1A2A3…∮AN-1AN 之結果。

(請翻頁繼續作答)

 

 

聰明的你很快就發現了幾件重要的事實:

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時,依照不同的順序會需要不同的彼彼運算次數。

例如:要計算ABC的話,有兩種選擇:

(AB) C 或者 (A(BC))

 

假設A7x10的矩陣,B10x22的矩陣,C22x37的矩陣,則

(AB) C需要(7*10*22) + (7*22*37) = 7238次彼彼運算

A(BC) 需要(10*22*37)+(7*10*37) = 10730次彼彼運算

5.     雖然利用其它的特殊技巧可以更快速的計算出答案,但為了防止自己算錯,你決定只利用添加括號的方式來加快運算速度(也就是改變運算的順序)。

 

根據你不平凡的智力,計算500次彼彼運算需要一張A4白紙,因此一張雙面A4總共可計算1000次,因為此次入學考試由正直的DE親自監考,正直的DE常常懷疑學生不正直,故你最好事先計算出最低所需的計算紙數量,以免當天考試因為帶太多計算紙而被正直的DE懷疑你的身份!

 

 

輸入說明 :

 

輸入檔以一個數字T為開頭,代表題目卷共有T個小題(1<=T<=5)。

每個小題以一個整數N1<=N<= 1000),代表有幾個矩陣需要做運算,接著有N行輸入,RiCi分別代表矩陣AiRowColumn大小(1<=Ri<=1000 1<=Ci<=10001<=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

提示 :

出處 :

2007 NPSC 高中組決賽



作法 : 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;
}

台長: Morris
人氣(974) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:d946. D. 阿克圖洛斯‧蒙斯克的煩惱
此分類上一篇:d934. F. Lisa 的圍巾

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文