• <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>

            Toj Lawrence of Arabia 四邊形不等式優化

             1 /* 
             2  * File:   Toj 3305.cpp
             3  * Author: GongZhi
             4  * Problem: 動態規劃,四邊形不等式優化
             5  * Created on 2009年7月27日, 上午12:00
             6  */
             7 
             8 #include <stdlib.h>
             9 #include <string.h>
            10 #include <iostream>
            11 #include <string>
            12 #include <vector>
            13 #include <map>
            14 #include <queue>
            15 using namespace std;
            16 
            17 /*
            18  *
            19  */
            20 #define MAXN 1100
            21 long long a[MAXN], sum1[MAXN], sum2[MAXN], f[MAXN][MAXN], w[MAXN][MAXN], p[MAXN][MAXN];
            22 
            23 int main() {
            24     int n, m, i, j, t, k;
            25     while (scanf("%d%d"&n, &m), n) {
            26         m++;
            27         for (i = 1; i <= n; i++)scanf("%d"&a[i]);
            28         sum1[0= 0;
            29         sum2[0= 0;
            30         for (i = 1; i <= n; i++)sum1[i] = sum1[i - 1+ a[i];
            31         for (i = 1; i <= n; i++)sum2[i] = sum2[i - 1+ a[i] * a[i];
            32         for (i = 1; i <= n; i++)
            33             for (j = 1; j <= n; j++)w[i][j] = ((sum1[j] - sum1[i - 1])*(sum1[j] - sum1[i - 1])-(sum2[j] - sum2[i - 1])) / 2;
            34         for (i = 1; i <= n; i++) {
            35             f[1][i] = w[1][i];
            36             p[1][i] = 1;
            37         }
            38         for (i = 2; i <= m; i++) {
            39             j = n;
            40             f[i][j] = 100000000000000ll;
            41             for (k = p[i - 1][j]; k <= j - 1; k++)
            42                 if (f[i - 1][k] + w[k + 1][j] < f[i][j]) {
            43                     f[i][j] = f[i - 1][k] + w[k + 1][j];
            44                     p[i][j] = k;
            45                 }
            46             for (j = n - 1; j >= 1; j--) {
            47                 f[i][j] = 100000000000000ll;
            48                 for (k = p[i - 1][j]; k <= p[i][j + 1]; k++)
            49                     if (f[i - 1][k] + w[k + 1][j] < f[i][j]) {
            50                         f[i][j] = f[i - 1][k] + w[k + 1][j];
            51                         p[i][j] = k;
            52                     }
            53             }
            54         }
            55         printf("%d\n", f[m][n]);
            56     }
            57     return 0;
            58 }
            59 
            60 

            posted on 2009-07-27 00:44 gong 閱讀(1590) 評論(4)  編輯 收藏 引用

            評論

            # re: Toj Lawrence of Arabia 四邊形不等式優化 2009-07-27 09:48 李錦俊

            看著這種代碼我就會頭暈。能不能寫點注釋?另外建議少用點magic number。
              回復  更多評論   

            # re: Toj Lawrence of Arabia 四邊形不等式優化 2009-07-29 21:21 Vincent

            贊一個  回復  更多評論   

            # re: Toj Lawrence of Arabia 四邊形不等式優化 2009-09-07 23:50 baiqi2piao

            很贊啊。8錯的代碼  回復  更多評論   

            # re: Toj Lawrence of Arabia 四邊形不等式優化 2009-10-04 03:37 XsugarX

            受教了~哈哈哈  回復  更多評論   

            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            常用鏈接

            留言簿(6)

            隨筆檔案

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            評論排行榜

            久久九九精品99国产精品| 久久这里的只有是精品23| 亚洲欧美另类日本久久国产真实乱对白| 国产精品久久99| 精品久久综合1区2区3区激情| 国产午夜电影久久| 婷婷五月深深久久精品| 国产精品VIDEOSSEX久久发布| 久久成人永久免费播放| 麻豆精品久久久久久久99蜜桃| 91精品国产综合久久精品| 久久WWW免费人成—看片| 77777亚洲午夜久久多人| 青草久久久国产线免观| 国产精品久久久久9999高清| 久久天天日天天操综合伊人av| 日本福利片国产午夜久久| 97久久国产综合精品女不卡| 亚洲乱亚洲乱淫久久| 91超碰碰碰碰久久久久久综合| 婷婷国产天堂久久综合五月| 久久这里只有精品久久| 色诱久久久久综合网ywww| 久久精品国产亚洲AV麻豆网站| 久久久久99精品成人片| 伊人久久大香线蕉综合热线| 日本福利片国产午夜久久| 无码国内精品久久人妻蜜桃| 日日狠狠久久偷偷色综合免费| 中文字幕久久欲求不满| 国产精品99久久久久久人| 亚洲愉拍99热成人精品热久久| 久久夜色精品国产亚洲av| 国产三级精品久久| 久久精品国产亚洲Aⅴ蜜臀色欲| 国产一级持黄大片99久久| 中文字幕一区二区三区久久网站| 久久久久亚洲AV无码网站| 欧美va久久久噜噜噜久久| 伊人久久大香线蕉综合Av| 亚洲综合精品香蕉久久网|