zhx and contest (枚举　 +　ｄｆｓ）

zhx and contest

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 324 Accepted Submission(s): 118

Problem Description

As one of the most powerful brushes in the world, zhx usually takes part in all kinds of contests. One day, zhx takes part in an contest. He found the contest very easy for him. There are

Input

Multiply test cases(less than

Output

For each test case, output a single line indicating the answer. If zhx is able to get enough points, output the minimal time it takes. Otherwise, output a single line saying "zhx is naive!" (Do not output quotation marks).

Sample Input

Sample Output

7 8 zhx is naive!

Source

BestCoder Round #33

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cassert>
  5 #include <climits>
  6 #include <ctime>
  7 #include <numeric>
  8 #include <vector>
  9 #include <algorithm>
 10 #include <bitset>
 11 #include <cmath>
 12 #include <cstring>
 13 #include <iomanip>
 14 #include <complex>
 15 #include <deque>
 16 #include <functional>
 17 #include <list>
 18 #include <map>
 19 #include <string>
 20 #include <sstream>
 21 #include <set>
 22 #include <stack>
 23 #include <queue>
 24 using namespace std;
 25 template<class T> inline T sqr(T x) { return x * x; }
 26 typedef long long LL;
 27 typedef unsigned long long ULL;
 28 typedef long double LD;
 29 typedef pair<int, int> PII;
 30 typedef pair<PII, int> PIII;
 31 typedef pair<LL, LL> PLL;
 32 typedef pair<LL, int> PLI;
 33 typedef pair<LD, LD> PDD;
 34 #define MP make_pair
 35 #define PB push_back
 36 #define sz(x) ((int)(x).size())
 37 #define clr(ar,val) memset(ar, val, sizeof(ar))
 38 #define istr stringstream
 39 #define FOR(i,n) for(int i=0;i<(n);++i)
 40 #define forIt(mp,it) for(__typeof(mp.begin()) it = mp.begin();it!=mp.end();it++)
 41 const double EPS = 1e-6;
 42 const int INF = 0x3fffffff;
 43 const LL LINF = INF * 1ll * INF;
 44 const double PI = acos(-1.0);
 45 
 46 #define lson l,mid,rt<<1
 47 #define rson mid+1,r,rt<<1|1
 48 #define lowbit(u) (u&(-u))
 49 
 50 using namespace std;
 51 
 52 #define MAXN 35
 53 
 54 struct Question{
 55     int t,v,l;
 56     bool operator<(const Question& q) const{
 57         return l - t < q.l - q.t ;
 58     }
 59 } q[MAXN];
 60 
 61 LL remain[MAXN];
 62 int n,w;
 63 
 64 bool dfs(int cur,int t,LL val){
 65     if(val>=w) return true;
 66     if(cur<0) return false;
 67     if(val+remain[cur]<w) return false;
 68     if(t>=q[cur].l&&t>=q[cur].t)
 69         if(dfs(cur-1,t-q[cur].t,val+q[cur].v)) return true;
 70     if(dfs(cur-1,t,val)) return true;
 71     return false;
 72 }
 73 
 74 int main(void){
 75 #ifndef ONLINE_JUDGE
 76     freopen("a.txt","r",stdin);
 77 #endif
 78     while(scanf("%d %d",&n,&w)!=EOF){
 79         LL sum = 0;
 80         FOR(i,n) scanf("%d %d %d",&q[i].t,&q[i].v,&q[i].l);
 81         sort(q,q+n);
 82         for(int i = 0;i<n;i++){
 83             if(i==0) remain[i] = q[i].v;
 84             else remain[i] = remain[i-1]+q[i].v;
 85         }
 86         if(remain[n-1]<w){
 87             puts("zhx is naive!");
 88             continue;
 89         }
 90         int ans = INF;
 91         int low = 0,high = 100000*n;
 92         while(low<=high){
 93             int mid = (low+high)>>1;
 94             if(dfs(n-1,mid,0)){
 95                 high = mid-1;
 96                 ans = mid;
 97             }else low = mid+1;
 98         }
 99         printf("%d
",ans);
100     }
101     return 0;
102 }

View Code

一个简单的想法是状态压缩dp。
但是30

zhx and contest (枚举 + ｄｆｓ）

zhx and contest

zhx and contest (枚举　 +　ｄｆｓ）