求助,7个WA,记搜三维数组
查看原帖
求助,7个WA,记搜三维数组
984551
SingKwenCat楼主2023/4/28 19:57

找了好久找不到问题,求各位大佬帮忙找找,谢谢

#include <bits/stdc++.h>

using namespace std;

const int N = 60;

int mem[N][N][N];
int h0,t0,n,t[N],h[N],k[N];

int dfs(int i, int hh, int tt){
	if (mem[i][hh][tt]) return mem[i][hh][tt];
	int res;
	if (i == n-1) if (hh >= h[i] && tt >= t[i]) res = k[i];
		else res = 0;
	else if (hh < h[i] || tt < t[i]) res = dfs(i+1, hh, tt);
		else res = max(dfs(i+1, hh - h[i], tt - t[i]) + k[i], dfs(i+1, hh, tt));
	mem[i][hh][tt] = res;
	return res;
}

int main(){
	memset(mem, 0, sizeof mem);
	scanf("%d%d%d", &h0, &t0, &n);
	for (int i = 0; i < n; i++) scanf("%d%d%d", &h[i], &t[i], &k[i]);
	int ans = dfs(0, h0, t0);
	printf("%d", ans);
	return 0;
}
2023/4/28 19:57
加载中...