70pts 玄关
  • 板块P1833 樱花
  • 楼主fjh0531
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/20 13:14
  • 上次更新2023/10/22 13:05:37
查看原帖
70pts 玄关
952663
fjh0531楼主2023/10/20 13:14
#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,d) for(int a=b;a<=d;a++)

const int MAXN=10001;
int tsh,tsm,teh,tem;
int n,cnt;
int t[MAXN],c[MAXN],p[MAXN];
int T;
int a;
int dp[MAXN][1001];
int pdp[101][1001];
int v[101];
int main()
{
    scanf("%d:%d %d:%d %d",&tsh,&tsm,&teh,&tem,&n);
    for(int i=1; i<=n; i++) cin>>t[i]>>c[i]>>p[i];
    T=(teh-tsh)*60+tem-tsm;
    for(int i=1; i<=n; i++)
    {
        for(int k=0; k<=T; k++)
        {
            dp[i][k]=dp[i-1][k];
        }
        if(p[i]==0) rep(k,1,T) if(k-t[i]>=0) dp[i][k]=max(dp[i][k-t[i]]+c[i],dp[i][k]);
        if(p[i]>=1)
        {
            cnt=1;
            a=1;
            while(p[i]>=a)
            {
                v[cnt]=a;
                cnt++;
                a*=2;
                p[i]>>=1;
            }
            if(p[i]!=0)
            {
                v[cnt]=p[i];
                cnt++;
            }
            cnt--;
            rep(k,0,T) pdp[0][k]=dp[i][k];
            rep(m,1,cnt) rep(k,0,T) if(k-t[i]*v[m]>=0) pdp[m][k]=max(pdp[m-1][k],pdp[m-1][k-v[m]*t[i]]+v[m]*c[i]);
            else pdp[m][k]=pdp[m-1][k];
            rep(k,0,T) dp[i][k]=pdp[cnt][k];
        }

    }
    cout<<dp[n][T];

}

2023/10/20 13:14
加载中...