USACO3.44Raucous Rockers

USACO挂了一小时。。我坚持不懈的等。。终于打开了把3章最后一题交了可以安心的睡去了

之前题意没看清楚不知道要有序写了一状压结果TLE了再优化也TLE 后来想写状态转移时发现它必须有序放。。这下就简单多了

枚举所有最后状态找个最大值就OK 了

。。汗。。我刚交上又打不开了还好交得快

 1 /*
 2     ID: shangca2
 3     LANG: C++
 4     TASK: rockers
 5  */
 6 #include <iostream>
 7 #include<cstdio>
 8 #include<cstring>
 9 #include<algorithm>
10 #include<stdlib.h>
11 using namespace std;
12 int len[22];
13 int main()
14 {
15     freopen("rockers.in","r",stdin);
16     freopen("rockers.out","w",stdout);
17     int i,j,n,t,m,kk=0,ans=0;
18     cin>>n>>t>>m;
19     for(i = 0; i < n ; i++)
20     cin>>len[i];
21     for(i = 0 ; i< (1<<n) ; i++)
22     {
23         int o=1,k=t,s=0;
24         for(j = 0 ; j < n ; j++)
25         {
26             if(i&(1<<j))
27             {
28                 if(k>=len[j])
29                 {
30                     k-=len[j];
31                     s++;
32                     continue;
33                 }
34                 else
35                 {
36                     k = t;
37                     o++;
38                 }
39                 if(o>m) break;
40                 if(k>=len[j])
41                 {
42                     k-=len[j];
43                     s++;
44                 }
45             }
46         }
47         if(j==n)
48         {
49             ans = max(ans,s);
50         }
51 
52     }
53     cout<<ans<<endl;
54     return 0;
55 }

View Code