xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

int  N,M;
int  f[ 501 ][ 501 ] = { 0 };
int  a[ 501 ] = { 0 };
int  b[ 501 ] = { 0 };
int  main()
{
    cin
>> N >> M;
    
int  x = 0 ;
    
for ( int  i = 1 ;i <= M; ++ i)
        
for ( int  j = 1 ;j <= N; ++ j)
            f[i][j]
= 0xFFFFFFF ;
    
for ( int  i = 1 ;i <= N; ++ i){
        cin
>> x;
        a[i]
= a[i - 1 ];
        b[i]
= b[i - 1 ];
        
if (x) a[i] ++ ;
        
else  b[i] ++ ;
        f[
1 ][i] = a[i] * b[i];
    }
    
for ( int  i = 2 ;i <= M; ++ i)
        
for ( int  j = i;j <= N; ++ j){
            
for ( int  t = i - 1 ;t < j; ++ t)
                
if (f[i][j] > f[i - 1 ][t] + (a[j] - a[t]) * (b[j] - b[t]))
                    f[i][j]
= f[i - 1 ][t] + (a[j] - a[t]) * (b[j] - b[t]);
        }
    cout
<< f[M][N] << endl;
    
return   0 ;
}





posted on 2009-06-04 00:45 xfstart07 阅读(157) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理