求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或**提早**）去上学。——摘自题目描述
by GalilAR @ 2023-07-04 11:37:18
试一下，不要设置s[k]位并在把背包输入数据处理完后一起进行dp数组的更新。
而是在每个背包输入进来的时候就去进行dp数组的更新。你可以参考一下我的代码。
```cpp
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
#define MAXN 10010
int t, h1, h2, m1, m2, m, w[MAXN], v[MAXN], idx;
long long dp[1010];
int main(){
scanf("%d:%d %d:%d %d", &h1, &m1, &h2, &m2, &m);
t = ( h2 - h1 )*60 + m2 - m1;
for( int i = 0 ; i < m ; i ++ ){
int c = 1 , ww, vv, n;
cin >> ww >> vv >> n;
if( !n )
for( int j = ww ; j <= t ; j ++ ) dp[j] = max( dp[j] , dp[j - ww] + vv);
else if( n == 1 )
for( int j = t ; j >= ww ; j -- ) dp[j] = max( dp[j] , dp[j - ww] + vv);
else{
idx = 0;
while( n > c ){
n -= c;
w[ ++ idx ] = c * ww;
v[ idx ] = c * vv;
c *= 2;
}
w[ ++ idx ] = n * ww;
v[ idx ] = n * vv;
for( int i = 1 ; i <= idx ; i ++ ){
for( int j = t ; j >= w[i] ; j -- ){
dp[j] = max( dp[j] , dp[j - w[i]] + v[i] );
}
}
}
}
cout << dp[t] << endl;
}
```
by Lycorisjzy @ 2023-07-29 20:44:00
谢谢大佬@[jzysama](/user/932956)
AC了
by NsSe_ @ 2023-08-02 11:26:17