c[i]是不是跟我有仇
  • 板块P1833 樱花
  • 楼主ZeroF
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/1/12 12:15
  • 上次更新2023/10/28 12:29:17
查看原帖
c[i]是不是跟我有仇
385165
ZeroF楼主2022/1/12 12:15
#include<iostream>
#include<cstdio>
using namespace std;
int c[10010],w[10010],n[10010];
int nc[100010],nw[10010];
int dp[10010];
int main(){
    int a,b,c,d,nn,v;
    scanf("%d%c%d%c%d%c%d%c%d",&a,&b,&c,&d,&nn);
    v=(a*60+b)-(c*60+d);
    for(int i=1;i<=nn;i++) {
        scanf("%d%d%d",&c[i],&w[i],&n[i]);
        if(n[i]==0){
        	n[i]=999999;
		}
    }
	int ncnt=0;
    for(int i=1;i<=nn;i++){
        int k;
        for(k=1;n[i]-(1<<k)+1>0;++k){
            nc[ncnt]=(1<<(k-1))*c[i];
            nw[ncnt]=(1<<(k-1))*w[i];
            ++ncnt;
            
        }
        --k;
        nc[ncnt]=(n[i]-(1<<k)+1)*c[i];
        nw[ncnt]=(n[i]-(1<<k)+1)*w[i];
        ++ncnt;
    }
    for(int i=0;i<ncnt;i++){
        for(int j=v;j>=nc[i];j--){
            dp[j]=max(dp[j],dp[j-nc[i]]+nw[i]);
        }
    }
    printf("%d\n",dp[v]);
    return 0;
}

2022/1/12 12:15
加载中...