11、堆砖块--2017网易春招

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5  
 6 const int maxh=500000+5;
 7 int a[55];
 8 int d[2][maxh];
 9  
10 int main()
11 {
12     int n;
13     while(cin>>n)
14     {
15         int sum = 0;
16         int a[n+1];
17         for(int i=1;i<=n;i++)
18         {
19             cin>>a[i];
20             sum+=a[i];
21         }
22         memset(d[0],-1,sizeof(d[0]));
23         d[0][0]=0;
24         for(int i=1;i<=n;i++)
25         {
26             for(int j=0;j<=sum;j++)
27             {
28                 d[i&1][j]=d[(i-1)&1][j];
29                 if(j+a[i]<=sum && d[(i-1)&1][j+a[i]]>=0)
30                     d[i&1][j]=max(d[i&1][j],d[(i-1)&1][j+a[i]]+a[i]);
31                 if(a[i]-j>=0 && d[(i-1)&1][a[i]-j]>=0)
32                     d[i&1][j]=max(d[i&1][j],d[(i-1)&1][a[i]-j]+a[i]-j);
33                 if(j-a[i]>=0 && d[(i-1)&1][j-a[i]]>=0)
34                     d[i&1][j]=max(d[i&1][j],d[(i-1)&1][j-a[i]]);
35             }
36         }
37         if(d[n&1][0]==0)
38             cout<<-1<<endl;
39         else
40             cout<<d[n&1][0]<<endl;
41     }
42     return 0;
43 }