• <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久久久久| 伊人色综合久久| 2021最新久久久视精品爱| 久久久久亚洲AV成人片| 久久电影网| 伊人久久大香线蕉AV色婷婷色 | 午夜精品久久久久久久久| 亚洲成色www久久网站夜月| 办公室久久精品| 日产精品久久久一区二区| 精品久久久久久无码人妻蜜桃| 无码人妻久久一区二区三区免费丨 | 伊人久久无码中文字幕| 亚洲一区中文字幕久久| 亚洲成色www久久网站夜月| AA级片免费看视频久久| 亚洲中文字幕久久精品无码喷水| 中文字幕一区二区三区久久网站| 亚洲欧美日韩中文久久| 久久亚洲av无码精品浪潮| 国产精品久久久天天影视| 亚洲AV无码久久精品狠狠爱浪潮| 久久av高潮av无码av喷吹| 9久久9久久精品| 久久夜色精品国产噜噜亚洲AV| 国产精品久久新婚兰兰| 久久久久亚洲AV无码专区桃色| 日本道色综合久久影院| 精品久久久久香蕉网| 亚洲va久久久噜噜噜久久| 久久久精品国产免大香伊 | 久久国产精品无| 精品久久久久久久久免费影院| 久久久久女教师免费一区| 久久露脸国产精品| 少妇被又大又粗又爽毛片久久黑人 | 日本免费久久久久久久网站| avtt天堂网久久精品| 久久精品国产亚洲AV无码麻豆 |