xfstart07
Get busy living or get busy dying

#include < fstream >
using   namespace  std;

int  n;
int  a[ 101 ];
int  f[ 101 ][ 101 ];
int  s[ 101 ][ 101 ];
int  main()
{
    ifstream cin(
" stone.in " );
    ofstream cout(
" stone.out " );
    cin
>> n;
    
for ( int  i = 1 ;i <= n; ++ i)
        cin
>> a[i];
    
int  MAX = 0x7FFFFFFF ;
    
for ( int  ti = 1 ;ti <= n; ++ ti){
        
if (ti != 1 ){
            
int  tmp = a[ti]; a[ti] = a[ti - 1 ]; a[ti - 1 ] = tmp;
        }
        memset(f,
0x7F , sizeof (f));
        memset(s,
0x7F , sizeof (s));
        
for ( int  i = 1 ;i <= n; ++ i){
            f[i][i]
= a[i];
            s[i][i]
= 0 ;
        }
        
for ( int  k = 2 ;k <= n; ++ k)
            
for ( int  i = 1 ;i <= n - k + 1 ; ++ i){
                
int  j = i + k - 1 ;
                
for ( int  t = j - 1 ;t >= i; -- t)
                    
if (f[i][j] > f[i][t] + f[t + 1 ][j]){
                        f[i][j]
= f[i][t] + f[t + 1 ][j];
                        
if (s[i][j] > f[i][j] + s[i][t] + s[t + 1 ][j])
                            s[i][j]
= f[i][j] + s[i][t] + s[t + 1 ][j];
                    }
                    
else   if (f[i][j] == f[i][t] + f[t + 1 ][j]){
                        
if (s[i][j] > f[i][j] + s[i][t] + s[t + 1 ][j])
                            s[i][j]
= f[i][j] + s[i][t] + s[t + 1 ][j];
                    }
            }
        
if (s[ 1 ][n] < MAX) MAX = s[ 1 ][n];
        
if (ti != 1 ){
            
int  tmp = a[ti]; a[ti] = a[ti - 1 ]; a[ti - 1 ] = tmp;
        }
    }
    cout
<< MAX << endl;
    
return   0 ;
}





posted on 2009-05-01 16:53 xfstart07 阅读(141) 评论(0)  编辑 收藏 引用 所属分类: 代码库

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