【Vijos1159】岳麓山上打水 [迭代加深]

今天算是学到了，到一些OJ上提交程序需要选择语言，不然会炸QAQ（大概是我太菜了现在才知道）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=100+10;
 4 const int M=20000+10;
 5 int n,m,k[N],mk,dp[M],t[N];
 6 bool fin=0;
 7 int rd()
 8 {
 9     int x=0,w=0;char ch=0;
10     while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
11     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
12     return w?-x:x;
13 }
14  
15 int check(int sum)
16 {
17     if(!sum) return dp[sum]=1;//可以接走 
18     if(!dp[sum]) return dp[sum];//之前已经试过不可以接走 
19     for(int i=1;i<=mk;i++)
20     if(sum>=t[i]&&check(sum-t[i]))
21     return dp[sum]=1;
22     return dp[sum]=0;
23 }
24  
25 void dfs(int cur,int dep)//第几种 有几种 
26 {
27     if(dep==mk+1)
28     {
29         memset(dp,-1,sizeof(dp)); 
30         if(check(m))
31         {
32             fin=1;
33             return;
34         }
35         return;
36     }
37     if(cur>n||fin) return;
38     t[dep]=k[cur];
39     dfs(cur+1,dep+1);
40     dfs(cur+1,dep);
41 }
42  
43 int main()
44 {
45     m=rd(),n=rd();
46     for(int i=1;i<=n;i++)
47     k[i]=rd();
48     sort(k+1,k+n+1);
49     for(mk=1;mk<=n;mk++)//枚举最大深度 
50     {
51         dfs(1,1);
52         if(fin==1)
53         {
54             printf("%d ",mk);
55             for(int i=1;i<=mk;i++)
56             printf("%d ",t[i]);
57             return 0;
58         }
59     }
60  }