get了很多新技能

當時想到了用dfs，但是排序用的是限制時間排序，一直沒搞出來。

正解：

二分用時，dfs判斷，為了順利進行做題，需要按照做題開始時間排序

還可以用dp

題意：

作為史上最強的刷子之一，zhx常常參與各種比賽。 有一天，zhx去虐一場比賽。他覺得題太簡單了。 這場比賽有n道題。他一眼就已經計算出他做第i道題要花ti的時間，做完后可以得到vi分。 因為他太強了，所以他被管理員盯上了。如果他在第li個單位時間前做完了第i道題，那么管理員就會認為他在作弊，然后把他的號封了。 zhx不一定把所有題都做完。他只需要拿到不少于w分就滿足了。他讓你告訴他他最小需要花費多少時間才能拿到足夠的分數并且不被封號。或者說他根本不能拿到那么多分。 注意，zhx只能同時做一道題，而且他一旦開始做一道題，就非得把它做出來不可。然后他會在做完后立即提交代碼。
1 3 1 4 7 3 6 4 1 8 6 8 10 1 5 2 2 7 10 4 1 10 2 3

7 8 zhx is naive! ? ? 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=35; 6 long long sum[maxn]; 7 int n,w; 8 struct node 9 { 10 int t,v,l; 11 void input() 12 { 13 scanf("%d%d%d",&t,&v,&l); 14 } 15 friend bool operator<(node a,node b) 16 { 17 return a.l-a.t<b.l-b.t; 18 } 19 }q[maxn]; 20 bool dfs(int p,int tot,long long va) 21 { 22 if(va>=w) return 1; 23 if(p<0) return 0; 24 if(va+sum[p]<w) return 0; //如果加上剩下的價值仍小于w 25 if(tot-q[p].l>=0&&tot-q[p].t>=0) if(dfs(p-1,tot-q[p].t,va+q[p].v)) return 1; 26 if(dfs(p-1,tot,va)) return 1; 27 return 0; 28 } 29 int main() 30 { 31 #ifndef ONLINE_JUDGE 32 freopen("1.in","r",stdin); 33 #endif 34 int i,j,k; 35 while(scanf("%d%d",&n,&w)!=EOF) 36 { 37 for(i=0;i<n;i++) q[i].input(); 38 sort(q,q+n); 39 /*for(int i=0;i<n;i++) 40 { 41 printf("%d %d %d\n",q[i].t,q[i].v,q[i].l); 42 }*/ 43 for(i=0;i<n;i++) 44 { 45 if(i==0) sum[i]=q[i].v; 46 else sum[i]=sum[i-1]+q[i].v; 47 } 48 if(sum[n-1]<w) 49 { 50 printf("zhx is naive!\n"); 51 continue; 52 } 53 int l=0,r=100000*n; //最高用時 54 int ans; 55 while(l<=r) 56 { 57 int mid=(l+r)>>1; 58 if(dfs(n-1,mid,0)) r=mid-1,ans=mid; 59 else l=mid+1; 60 } 61 printf("%d\n",ans); 62 } 63 }

?

轉載于:https://www.cnblogs.com/cnblogs321114287/p/4338972.html

總結

以上是生活随笔為你收集整理的hdu 5188 dfs+二分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。