C++14(g++5.4) 解法, 执行用时: 16ms, 内存消耗: 380K, 提交时间: 2020-09-23 21:50:41

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

struct gw{
    int a,b,c;
}g[100];
int n,ak,hp;
int dg(int p,int hp){
    int t=(g[p].b)/ak;
    if((g[p].b)%ak>0) t++;
    return hp-g[p].a*(t-1);
}
int dfs(int x,int hp,int c){
    int res=0;
    if(x == n+1 ) return 0;
    int h = dg(x,hp);
    if(h>0){
        if(c+g[x].c>=10) h=::hp;
        res = max(dfs(x+1,hp,c),dfs(x+1,h,(c+g[x].c)%10)+(c+g[x].c)/10);
    }
    else res = dfs(x+1,hp,c);
    return res;
}

int main(){
    scanf("%d%d%d",&n,&ak,&hp);
    for(int i=1;i<=n;i++){ scanf("%d%d%d",&g[i].a,&g[i].b,&g[i].c); }
    int ans=dfs(1,hp,0);
    printf("%d\n",ans);
    
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 380K, 提交时间: 2020-09-22 18:56:19

#include<iostream>
using namespace std;
int n,ak,hp,a[2007],b[2007],c[2007];
int cal(int p,int h){
	int time;
	if(b[p]%ak==0){
		time=b[p]/ak;
	}
	else time=b[p]/ak+1;
	return h-(time-1)*a[p];
}
int dfs(int p,int h,int z){
	if(p==n+1)return 0;
	int H=cal(p,h);
	if(H>0){
		if(z+c[p]>=10){
			H=hp;
		}
		return max(dfs(p+1,h,z),dfs(p+1,H,(z+c[p])%10)+(z+c[p])/10);
	}
	else{
		return dfs(p+1,h,z);
	}
}
int main(){
	scanf("%d%d%d",&n,&ak,&hp);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
	}
	printf("%d\n",dfs(1,hp,0));
}