背景:退役选手怎样保持码力呢?比较愉悦的方式是刷水题!于是我就把bzoj1600-1699按AC倒序排序开始刷了.

裸背包.可以压位优化一波(用bitset把复杂度从O(mn)降到O(nm/32)),但是数据范围太小并不需要.

这年头noip提高组除了day1t1都出不了这么水的题了...

#include
    
     bool w[50005];int main(){  w[0]=true;  int m,n;scanf("%d%d",&m,&n);  int x;  for(int i=1;i<=n;++i){    scanf("%d",&x);    for(int j=m;j>=x;--j)w[j]|=w[j-x];  }  while(!w[m])m--;  printf("%d\n",m);  return 0;}