#include  < iostream >

using   namespace  std;

#define  N 100001

int  nk[ 11 ], dk[ 11 ], n, m, ans[N], num[N];

int  main(){
    
while ( scanf( " %d%d " , & m, & n ) !=  EOF ){
        
for int  i =   0 ; i <  n;  ++ i ) scanf( " %d%d " , nk +  i, dk +  i );
        
for int  i =   0 ; i <=  m;  ++ i ) ans[i] =   0 ; ans[ 0 ] =   1 ;
        
        
for int  i =   0 ; i <  n;  ++ i ){
            
for int  j =   0 ; j <=  m;  ++ j ) num[j] =   0 ;
            
            
for int  j =  dk[i]; j <=  m;  ++ j )
            
if !  ans[j]  &&  ans[j - dk[i]]  &&  num[j -  dk[i]] <  nk[i] ){
                num[j]
=  num[j - dk[i]] +   1 ;
                ans[j]
=   1 ; }
        }
        
        
int  res =  m;
        
while ( ans[res] ==   0   &&  res >=   1  ) res -- ;
        printf(
" %d\n " , res );
    }
    
    
return   0 ;
}
posted on 2009-07-19 13:44 Darren 阅读(515) 评论(1)  编辑 收藏 引用 所属分类: 动态规划

评论:
# re: Pku 1276 Cash Machine 2009-08-17 12:24 | superlong
你这个是0MS吧 算是强剪枝了  回复  更多评论
  

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