xfstart07
Get busy living or get busy dying


#include < iostream >   
using   namespace  std;  
  
int  n,f[ 101 ][ 101 ],s[ 101 ][ 101 ];  
int  main()  
{  
    scanf(
" %d " , & n);  
    
for ( int  i = 1 ;i <= n; ++ i)  
        
for ( int  j = 1 ;j <= n; ++ j)  
            s[i][j]
= f[i][j] = 0xFFFFFFF ;  
    
for ( int  i = 1 ;i <= n; ++ i){  
        scanf(
" %d " , & f[i][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];  
                    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];  
        }  
    }  
    printf(
" %d\n " ,s[ 1 ][n]);  
    
return   0 ;  
}

rq490
#include<cstdio>
using namespace std;

typedef 
int Arr[210][210];
int N;
Arr M1,M2,S1,S2;
int main()
{
    scanf(
"%d",&N);
    
for(int i=1;i<=N;++i){
        
int a; scanf("%d",&a);
        M1[i][i]
=M2[i][i]=M1[i+N][i+N]=M2[i+N][i+N]=a;
        S1[i][i]
=S2[i][i]=S1[i+N][i+N]=S2[i+N][i+N]=0;
    }
    
for(int k=2;k<=N;++k){
        
for(int i=1;i<=2*N-k+1;++i){
            
int j=i+k-1;
            M1[i][j]
=S1[i][j]=0xFFFFFFF;
            M2[i][j]
=S2[i][j]=0;
            
for(int t=j-1;t>=i;--t){
                
if(M1[i][j]>M1[i][t]+M1[t+1][j]){
                    M1[i][j]
=M1[i][t]+M1[t+1][j];
                    
if(S1[i][j]>M1[i][j]+S1[i][t]+S1[t+1][j])
                        S1[i][j]
=M1[i][j]+S1[i][t]+S1[t+1][j];
                }
                
else if(M1[i][j]==M1[i][t]+M1[t+1][j]){
                    
if(S1[i][j]>M1[i][j]+S1[i][t]+S1[t+1][j])
                        S1[i][j]
=M1[i][j]+S1[i][t]+S1[t+1][j];
                }
                
if(M2[i][j]<=M2[i][t]+M2[t+1][j]){
                    M2[i][j]
=M2[i][t]+M2[t+1][j];
                    
if(S2[i][j]<M2[i][j]+S2[i][t]+S2[t+1][j])
                        S2[i][j]
=M2[i][j]+S2[i][t]+S2[t+1][j];
                }
                
else if(M2[i][j]==M2[i][t]+M2[t+1][j]){
                    
if(S2[i][j]<M2[i][j]+S2[i][t]+S2[t+1][j])
                        S2[i][j]
=M2[i][j]+S2[i][t]+S2[t+1][j];
                }
            }
        }
    }
    
int ans=0xFFFFFFF;
    
for(int i=1;i<=N;++i)
        
if(S1[i][i+N-1]<ans)
            ans
=S1[i][i+N-1];
    printf(
"%d\n",ans);
    ans
=0;
    
for(int i=1;i<=N;++i)
        
if(S2[i][i+N-1]>ans)
            ans
=S2[i][i+N-1];
    printf(
"%d\n",ans);
    
return 0;
}



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

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