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


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