题目传送门
解题思路:
就是完全背包和多重背包的混合.处理时间的时候注意一下就行了
AC代码:
1 #include<iostream> 2 #include<cstdio> 3 4 using namespace std; 5 6 string l,l1; 7 int h1,h2,m1,m2,t,n,w[200001],c[200001],p1,f[1001]; 8 bool p,vis[200001]; 9 10 inline void find_time() { 11 cin >> l >> l1; 12 for(int i = 0;i < l.length(); i++) { 13 if(l[i] == ':') { 14 p = 1; 15 continue; 16 } 17 if(!p) h1 = h1 * 10 + (l[i] - '0'); 18 if(p) m1 = m1 * 10 + (l[i] - '0'); 19 } 20 p = 0; 21 for(int i = 0;i < l1.length(); i++) { 22 if(l1[i] == ':') { 23 p = 1; 24 continue; 25 } 26 if(!p) h2 = h2 * 10 + (l1[i] - '0'); 27 if(p) m2 = m2 * 10 + (l1[i] - '0'); 28 } 29 t = (h2 - h1) * 60 + (m2 - m1); 30 m2 = 0; 31 } 32 33 int main() { 34 find_time(); 35 scanf("%d",&n); 36 for(int i = 1;i <= n; i++) { 37 scanf("%d%d%d",&h1,&h2,&m1); 38 if(m1 == 0) { 39 w[++m2] = h1; 40 c[m2] = h2; 41 vis[m2] = 1; 42 } 43 else { 44 for(int j = 1;j <= m1; j *= 2) { 45 w[++m2] = h1 * j; 46 c[m2] = h2 * j; 47 m1 -= j; 48 } 49 if(m1 != 0) { 50 w[++m2] = h1 * m1; 51 c[m2] = h2 * m1; 52 } 53 } 54 } 55 for(int i = 1;i <= m2; i++) { 56 if(!vis[i]) 57 for(int j = t;j >= w[i]; j--) 58 f[j] = max(f[j],f[j-w[i]] + c[i]); 59 else 60 for(int j = w[i];j <= t; j++) 61 f[j] = max(f[j],f[j-w[i]] + c[i]); 62 } 63 printf("%d",f[t]); 64 return 0; 65 }