01背包——[Usaco2008 Dec]Hay For Sale

看到 5000*50000有点不敢做了……

其实bool数组很快

 
   
   #include 
   < 
   stdio.h 
   > 
   

 
   bool 
    f[ 
   50009 
   ];
 
   int 
    a[ 
   5009 
   ];

 
   int 
    main()
{
 
   int 
    c,n;
 
   while 
   (scanf( 
   " 
   %d%d 
   " 
   , 
   & 
   c, 
   & 
   n) 
   != 
   EOF)
 {
 
   int 
    i,j;
 
   for 
   (i 
   = 
   1 
   ;i 
   <= 
   c;i 
   ++ 
   )
 f[i] 
   = 
   0 
   ;
 
   for 
   (i 
   = 
   1 
   ;i 
   <= 
   n;i 
   ++ 
   )
 scanf( 
   " 
   %d 
   " 
   , 
   & 
   a[i]);

 f[ 
   0 
   ] 
   = 
   1 
   ;
 
   for 
   (i 
   = 
   1 
   ;i 
   <= 
   n;i 
   ++ 
   )
 {
 
   for 
   (j 
   = 
   c;j 
   >= 
   a[i];j 
   -- 
   )
 {
 
   if 
   (f[j 
   - 
   a[i]] 
   == 
   1 
   )
 f[j] 
   = 
   1 
   ;
 }
 
   if 
   (f[c] 
   == 
   1 
   ) 
   // 
   加速尽十倍 
   
 
     
   break 
   ;
 }

 
   for 
   (i 
   = 
   c;f[i] 
   == 
   0 
   ;i 
   -- 
   );

 printf( 
   " 
   %d\n 
   " 
   ,i);
 }
}