• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            dp_1_M

            最近開始刷奇奇神的dp專題,呃,我是弱菜,啥都不會,現在才開始刷dp,
            在nocLyt神的熏陶下,覺著區間dp有些感覺了
            不過還是調半天才調出來
            今天做的這個
            M - Optimal Array Multiplication Sequence
            Time Limit:3000MS     Memory Limit:0KB     64bit IO Format:%lld & %llu

            Description


             Optimal Array Multiplication Sequence 

            Given two arrays A and B, we can determine the array C = A B using the standard definition of matrix multiplication:

            The number of columns in the A array must be the same as the number of rows in the B array. Notationally, let's say that rows(A) and columns(A) are the number of rows and columns, respectively, in the A array. The number of individual multiplications required to compute the entire C array (which will have the same number of rows as A and the same number of columns as B) is then rows(A) columns(B) columns(A). For example, if A is a tex2html_wrap_inline67 array, and B is a tex2html_wrap_inline71 array, it will take tex2html_wrap_inline73 , or 3000 multiplications to compute the C array.

            To perform multiplication of more than two arrays we have a choice of how to proceed. For example, if X, Y, and Z are arrays, then to compute X Y Z we could either compute (X Y) Z or X (Y Z). Suppose X is a tex2html_wrap_inline103 array, Y is a tex2html_wrap_inline67 array, and Z is a tex2html_wrap_inline111 array. Let's look at the number of multiplications required to compute the product using the two different sequences:

            (X Y) Z

            • tex2html_wrap_inline119 multiplications to determine the product (X Y), a tex2html_wrap_inline123 array.
            • Then tex2html_wrap_inline125 multiplications to determine the final result.
            • Total multiplications: 4500.

            X (Y Z)

            • tex2html_wrap_inline133 multiplications to determine the product (Y Z), a tex2html_wrap_inline139 array.
            • Then tex2html_wrap_inline141 multiplications to determine the final result.
            • Total multiplications: 8750.

            Clearly we'll be able to compute (X Y) Z using fewer individual multiplications.

            Given the size of each array in a sequence of arrays to be multiplied, you are to determine an optimal computational sequence. Optimality, for this problem, is relative to the number of individual multiplications required.

            Input

            For each array in the multiple sequences of arrays to be multiplied you will be given only the dimensions of the array. Each sequence will consist of an integer N which indicates the number of arrays to be multiplied, and then N pairs of integers, each pair giving the number of rows and columns in an array; the order in which the dimensions are given is the same as the order in which the arrays are to be multiplied. A value of zero for N indicates the end of the input. N will be no larger than 10.

            Output

            Assume the arrays are named tex2html_wrap_inline157 . Your output for each input case is to be a line containing a parenthesized expression clearly indicating the order in which the arrays are to be multiplied. Prefix the output for each case with the case number (they are sequentially numbered, starting with 1). Your output should strongly resemble that shown in the samples shown below. If, by chance, there are multiple correct sequences, any of these will be accepted as a valid answer.

            Sample Input

            3 1 5 5 20 20 1 3 5 10 10 20 20 35 6 30 35 35 15 15 5 5 10 10 20 20 25 0

            Sample Output

            Case 1: (A1 x (A2 x A3)) Case 2: ((A1 x A2) x A3) Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))

            雖說這個是水題吧,但好歹是自己用心寫的一個dp,就放在這了,

            #include<stdio.h>
            #include
            <string.h>
            #include
            <math.h>
            #define inf 0x7ffffff
            #define maxn 15
            int f[maxn][maxn],path[maxn][maxn];
            int l[maxn],r[maxn];
            int n;
            int min(int a,int b)
            {
                
            return a<b?a:b;
            }
            void print(int h,int t)
            {
                printf(
            "(");
                
            if (t-h==1)
                {
                    printf(
            "A%d x A%d",h,t);
                }
                
            else
                {
                    
            int tmp=path[h][t];
                    
            if(tmp-h==0)
                    {
                        printf(
            "A%d x ",h);
                         
            if(t-tmp-1==0) printf("A%d",t);else print(tmp+1,t);
                    }
                    
            else if(t-tmp==0)
                    {
                        
                        
            if(h-tmp-1==0) printf("A%d",h);else print(h,tmp-1);
                        printf(
            " x A%d",t);
                    }
                    
            else
                    {
                        
            if(h-tmp==0) printf("A%d",h);else print(h,tmp);
                        printf(
            " x ");
                        
            if(t-tmp-1==0) printf("A%d",t);else print(tmp+1,t);
                    }
                }
                printf(
            ")");
            }
            int main()
            {
                
            int i,j,k,times;
                times
            =0;
                
            while(scanf("%d",&n)!=EOF&&n!=0)
                {
                    times
            ++;
                    
            for(i=1; i<=n; i++) scanf("%d%d",&l[i],&r[i]);
                    memset(f,
            0,sizeof(f));
                    
            for(i=1; i<=n-1; i++)
                        f[i][i
            +1]=l[i]*r[i]*r[i+1];//,printf("%d %d %d\n",i,i+1,f[i][i+1]);
                    for(i=n-2; i>=1; i--)
                    {
                        
            for(j=i+2; j<=n; j++)
                        {
                            f[i][j]
            =inf;
                            
            for(k=i; k<=j; k++)
                                
            if(f[i][k]+f[k+1][j]+l[i]*r[k]*r[j]<f[i][j])
                                {
                                    
            //printf("%d %d %d %d %d %d\n",i,k,j,f[i][k],f[k+1][j],l[i]*r[k]*r[j]);
                                    f[i][j]=f[i][k]+f[k+1][j]+l[i]*r[k]*r[j];
                                    path[i][j]
            =k;
                                }
                            
            //printf("%d %d %d %d\n",i,j,f[i][j],path[i][j]);
                        }
                    }
                    
            //printf("%d\n",f[1][n]);
                    printf("Case %d: ",times);
                    print(
            1,n);
                    printf(
            "\n");
                }
                
            return 0;
            }

            呃,我是water,那個這個還可以用記憶化dp來實現,不過我沒寫過很好的記憶化搜索,干脆每次都寫的遞推實現
            不過效率還好……

            posted on 2012-06-02 12:25 jh818012 閱讀(130) 評論(0)  編輯 收藏 引用

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿

            文章檔案(85)

            搜索

            最新評論

            • 1.?re: poj1426
            • 我嚓,,輝哥,,居然搜到你的題解了
            • --season
            • 2.?re: poj3083
            • @王私江
              (8+i)&3 相當于是 取余3的意思 因為 3 的 二進制是 000011 和(8+i)
            • --游客
            • 3.?re: poj3414[未登錄]
            • @王私江
              0ms
            • --jh818012
            • 4.?re: poj3414
            • 200+行,跑了多少ms呢?我的130+行哦,你菜啦,哈哈。
            • --王私江
            • 5.?re: poj1426
            • 評論內容較長,點擊標題查看
            • --王私江
            日本人妻丰满熟妇久久久久久| 久久99精品久久久久久噜噜| 成人资源影音先锋久久资源网| 久久久久亚洲av无码专区导航| 人妻丰满AV无码久久不卡| 亚洲国产精品无码久久久久久曰| 久久久噜噜噜久久中文字幕色伊伊 | 99久久这里只有精品| 91久久福利国产成人精品| 欧洲国产伦久久久久久久| 无码八A片人妻少妇久久| 国产99精品久久| 国产精品美女久久久久AV福利| 亚洲人AV永久一区二区三区久久| 亚洲精品tv久久久久| 国产韩国精品一区二区三区久久 | 久久偷看各类wc女厕嘘嘘| 777久久精品一区二区三区无码| 久久综合五月丁香久久激情| 久久国产高潮流白浆免费观看| 久久99精品国产麻豆婷婷| 亚洲va久久久噜噜噜久久狠狠| 亚洲国产精品综合久久一线 | 久久精品国产亚洲AV高清热| 欧美激情精品久久久久久久九九九| 日韩久久久久久中文人妻| 亚洲午夜精品久久久久久app| 日本一区精品久久久久影院| 久久亚洲私人国产精品vA| 久久青青草原精品国产软件| 久久国产乱子伦精品免费强| 人妻无码αv中文字幕久久| 久久久久亚洲精品天堂久久久久久| 2022年国产精品久久久久 | 久久亚洲国产最新网站| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 亚洲精品国产字幕久久不卡| 亚洲国产综合久久天堂 | 久久福利片| 久久婷婷五月综合色99啪ak| 国产L精品国产亚洲区久久|