C++14(g++5.4) 解法, 执行用时: 724ms, 内存消耗: 4444K, 提交时间: 2020-06-21 09:56:24

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
int a[maxn], b[maxn];
int dp[maxn];
int main()
{
    int x1,y1,x2,y2,n,s;
    scanf("%d:%d%d:%d%d",&x1,&y1,&x2,&y2,&n);
    s=(x2-x1)*60+y2-y1;
    int c = 0;
    for(int i=1;i<=n;i++)
    {
        int t,q,k; scanf("%d%d%d",&t,&q,&k);
        if(k==0||k>s/t) k = s/t;
        for(int x=1;x<=k;x<<=1) a[++c] = x * q , b[c] = x*t , k -= x;
        if(k) a[++c] = k*q, b[c] = k*t;
    }
    for(int i=1;i<=c;i++)
    {
        for(int j=s;j>=b[i];j--)
          dp[j] = max(dp[j],dp[j-b[i]]+a[i]);
    }
    printf("%d\n",dp[s]);
}

C++11(clang++ 3.9) 解法, 执行用时: 381ms, 内存消耗: 1252K, 提交时间: 2020-06-22 23:56:06

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

int main()
{
    int i,j,a,b,c,n,m,DP[1505]={0};
    scanf("%d:%d",&a,&b),c=a*60+b;
    scanf("%d:%d%d",&a,&b,&n),m=a*60+b-c;
    while(n--)
    {
    	scanf("%d%d%d",&a,&b,&c);
    	if(c)
    	{
    		for(i=1;i<=c;c-=i,i<<=1)
    			for(j=m;j>=i*a;j--)DP[j]=max(DP[j],DP[j-i*a]+i*b);
    		if(c)for(j=m;j>=c*a;j--)DP[j]=max(DP[j],DP[j-c*a]+c*b);
		}
		else for(i=a;i<=m;i++)DP[i]=max(DP[i],DP[i-a]+b);
	}
	printf("%d\n",DP[m]);
}