misschuer

常用链接

统计

积分与排名

百事通

最新评论

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 此最相思 阅读(152) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理