$dp_{i,j}$ 表示选前 $i$ 个物品,时间为 $j$ 的最大美值.

$cho_j$表示时间 $j$ 内获取最大美值看了几次树 $i$ .

状态转移如下情况:

$$dp_{i,j}=dp_{i-1,j},cho_j=0;$$

2.($j>=t_i$)

$$dp_{i,j}=dp_{i-1,j-t_{i}}+c_i , cho_j=1;$$

$$dp_{i,j}=dp_{i,j-1} , cho_j=cho_{j-1};$$

4.( $cho_j < p_i$ || $p_i==0$ && $j>=t_i$)

$$dp_{i,j}=dp_{i,j-t_i}+c_i , cho_j=cho_{j-t_i}+1;$$

在这之中取最大值并且更新 $cho_j$ 用于后续判断

代码如下:

#include<bits/stdc++.h>
using namespace std;

int dp[10004][1003];
int cho[1003];

int t[10004],c[10004],p[10004];

int sh,sm,eh,em;
int n,m;


void solve(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			
			if(dp[i][j]<dp[i][j-1]){
				dp[i][j]=dp[i][j-1];
				cho[j]=cho[j-1];
			}

			if(j>=t[i]){
				if(!p[i] || cho[j-t[i]]<p[i]){
					if(dp[i][j]<dp[i][j-t[i]]+c[i]){
						dp[i][j]=dp[i][j-t[i]]+c[i];
						cho[j]=cho[j-t[i]]+1;
					}
				}
				if(dp[i][j]<=dp[i-1][j-t[i]]+c[i]){
					dp[i][j]=dp[i-1][j-t[i]]+c[i];
					cho[j]=1;
				}
			}
				if(dp[i][j]<=dp[i-1][j]){
				dp[i][j]=dp[i-1][j];
				cho[j]=0;
			}
			
		}
	}
}

int main(){
	scanf("%d:%d %d:%d",&sh,&sm,&eh,&em);
	cin>>n;
	
	if(em-sm<0)m-=60;;
	m+=((em-sm)+60)%60;
	m+=60*(((eh-sh)+24)%24);
	
	for(int i=1;i<=n;i++){
		cin>>t[i]>>c[i]>>p[i];
	}
	
	solve();

	cout<<dp[n][m]<<'\n';

	return 0;
}