1 solutions
-
0
爱吃糖的dumpline题解
这道题的核心思路就是二分查找答案,因为单颗糖的最多就在1000,所以直接1——1000范围内二分check就行了 check就一个简单的01背包板子,但是加一个判断条件当当前这课糖的时间高于这个时间就跳过 如果在1000以内找到了答案直接输出否则就不行,输出dumpline很伤心!
#include<iostream> #include<queue> #include<algorithm> #include<string.h> #define PII pair<int,string> #include<math.h> #include<vector> #include<map> using namespace std; typedef long long ll; const int N=1e6+5; int h[N],t[N]; int dp[N]; int n,p,S; bool check(int k) { memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) { if(t[i]>k)continue;//当时间大于k的时候就跳过,不参与。 for(int j=p;j>=t[i];j--) { dp[j]=max(dp[j],dp[j-t[i]]+h[i]); } } return dp[p]>=S; } int main(){ cin>>n>>S>>p; for(int i=0;i<n;i++) { cin>>t[i]>>h[i]; } int l=1,r=1000; int mid; mid=(l+r)>>1; while(l<=r) { mid=(l+r)>>1; if(check(mid)) r=mid-1; else l=mid+1; } if(l<=1000)cout<<l<<"\n"; else cout<<"dumpline很伤心!\n"; return 0; }
- 1
Information
- ID
- 19
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 10
- Tags
- # Submissions
- 2
- Accepted
- 2
- Uploaded By