misschuer

公告

留言簿

隨筆分類

文章分類

acm (rss)
Java (rss)

隨筆檔案

文章檔案

2009年4月 (1)

閱讀排行榜

評論排行榜

常用鏈接

統計

隨筆 - 61
文章 - 1
評論 - 18
引用 - 0

積分與排名

積分 - 24973
排名 - 727

百事通

hao123
WPL
杭電
松松
星和

Pebble Merging

#include <iostream>

using namespace std;

int main()

{

int dpmin[ 200 ][ 200 ] , min[ 200 ][ 200 ] , mins;

int dpmax[ 200 ][ 200 ] , max[ 200 ][ 200 ] , maxs;

int a[ 200 ] , i , n , j , k , temp , l;

while (scanf ("%d" , & n) != EOF)

{

for (i = 1 ; i <= n ; ++ i)

scanf ("%d" , & a[ i ]);

for (i = 1 ; i < n ; ++ i)

a[i + n] = a[ i ];

for (i = 1 ; i < 2 * n ; ++ i)

{

min[ i ][ i ] = max[ i ][ i ] = 0;

dpmax[ i ][ i ] = dpmin[ i ][ i ] = a[ i ];

dpmax[ i ][i + 1] = dpmin[ i ][i + 1] = a[ i ] + a[i + 1];

min[ i ][i + 1] = max[ i ][i + 1] = a[ i ] + a[i + 1];

}

for (i = 1 ; i < n - 1; ++ i)

for (l = 1 , j = 2 + i ; j < 2 * n ; ++ j , ++ l)

{

for (k = l + 1 ; k <= j ; ++ k)

{

if (k == l + 1)

{

dpmin[ l ][ j ] = dpmin[ l ][k - 1] + dpmin[ k ][ j ] + min[ l ][k - 1] + min[ k ][ j ];

if ( l == k - 1 && k != j)

min[ l ][ j ] = a[ l ] + min[ k ][ j ];

else

if (l != k - 1 && k == j)

min[ l ][ j ] = min[ l ][k - 1] + a[ k ];

else

min[ l ][ j ] = min[ l ][k - 1] + min[ k ][ j ];

dpmax[ l ][ j ] = dpmax[ l ][k - 1] + dpmax[ k ][ j ] + max[ l ][k - 1] + max[ k ][ j ];

if ( l == k - 1 && k != j)

max[ l ][ j ] = a[ l ] + max[ k ][ j ];

else

if (l != k - 1 && k == j)

max[ l ][ j ] = max[ l ][k - 1] + a[ k ];

else

max[ l ][ j ] = max[ l ][k - 1] + max[ k ][ j ];

continue ;

}

temp = dpmin[ l ][k - 1] + dpmin[ k ][ j ] + min[ l ][k - 1] + min[ k ][ j ];

if (temp < dpmin[ l ][ j ])

{

dpmin[ l ][ j ] = temp;

if ( l == k - 1 && k != j)

min[ l ][ j ] = a[ l ] + min[ k ][ j ];

else

if (l != k - 1 && k == j)

min[ l ][ j ] = min[ l ][k - 1] + a[ k ];

else

min[ l ][ j ] = min[ l ][k - 1] + min[ k ][ j ];

}

temp = dpmax[ l ][k - 1] + dpmax[ k ][ j ] + max[ l ][k - 1] + max[ k ][ j ];

if (temp > dpmax[ l ][ j ])

{

dpmax[ l ][ j ] = temp;

if ( l == k - 1 && k != j)

max[ l ][ j ] = a[ l ] + max[ k ][ j ];

else

if (l != k - 1 && k == j)

max[ l ][ j ] = max[ l ][k - 1] + a[ k ];

else

max[ l ][ j ] = max[ l ][k - 1] + max[ k ][ j ];

}

mins = dpmin[ 1 ][ n ]; maxs = dpmax[ 1 ][ n ];

for (i = 2 ; i <= n ; ++ i)

{

if (mins > dpmin[ i ][i + n - 1])

mins = dpmin[ i ][i + n - 1];

if (maxs < dpmax[ i ][i + n - 1])

maxs = dpmax[ i ][i + n - 1];

}

printf ("%d\n%d\n" , mins , maxs);

}

return 23;

}

posted on 2009-04-21 19:25 此最相思閱讀(159) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

misschuer

導航

公告

留言簿

隨筆分類

文章分類

隨筆檔案

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

積分與排名

百事通

最新評論

Pebble Merging