xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

int  n,m;
int  a[ 15 ];
int  ans[ 15 ];
int  Max;
int  DP( int  l){
    
int  f[ 1000 ];
    f[
0 ] = 0 ;
    f[
1 ] = 1 ;
    
int  i = 1 ;
    
while (f[i] <= n){
        f[
++ i] = n + 1 ;
        
for ( int  j = 1 ;j <= l; ++ j)
            
if (i >= a[j])
                
if (f[i] > f[i - a[j]] + 1 )
                    f[i]
= f[i - a[j]] + 1 ;
        
if (f[i] == n + 1 return  i - 1 ;
    }
    
return  i;
}
void  dfs( int  k){
    
if (k == m){
        
int  tmp = DP(k);
        
if (tmp >= Max){
            Max
= tmp;
            memcpy(ans,a,
sizeof ( int ) * 15 );
        }
    }
    
else {
        
int  tmp = DP(k) + 1 ;
        
for ( int  i = a[k] + 1 ;i <= tmp; ++ i){
            a[k
+ 1 ] = i;
            dfs(k
+ 1 );
        }
    }
}
int  main()
{
    scanf(
" %d%d " , & n, & m);
    Max
= 0 ;
    a[
1 ] = 1 ;
    dfs(
1 );
    
for ( int  i = 1 ;i <= m; ++ i)
        printf(
" %d  " ,ans[i]);
    printf(
" \nMAX=%d\n " ,Max);
    
return   0 ;
}




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

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