广智正解相似但没过
一开始没有使用正解的dp,dp是i气力造成的最大伤害。所以我从0正向dp,f[i] >= hp时及得最小气力,but 不知道哪有问题,只能过16%
有没有大佬帮忙看一看
#include <bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define fo(i, n) for (int i = 1; i <= n; ++i) #define rep(i, k, n) for (int i = k; i <= n; ++i) #define inf 0x3f3f3f3f // #define int long long const int N = 1e6 + 1000; int hp; int a, b, c, d; int hp_k[N]; int f[N]; void solve() { cin >> hp; cin >> a >> b >> c >> d; fo(i, hp) { cin >> hp_k[i]; } fo(i,hp) { f[i]=0; } int ans = inf; for (int i = 1; i <= hp; ++i)//最多平A为hp(伤害最低1) { if (i < min(a, c)) f[i] = 0; if (i - a >= 0) f[i] = max(f[i - a] + b, f[i]); if (i - c >= 0) f[i] = max(f[i - c] + d, f[i]); int j = 4; if (i - j * a-c >= 0) f[i] = max(f[i], f[i - j * a - c] + j * b + d + hp_k[hp-f[i-c]]);//可疑点但是我没有证据 /* int delta=0; if(i-c-4*a>=0)delta=hp-f[i-c-4*a]-4*b; else delta=hp-f[i-c]; if (i - j * a-c >= 0) f[i] = max(f[i], f[i - j * a - c] + j * b + d + hp_k[delta]); */ if (f[i] >= hp) { ans = i; break; } } cout << ans << '\n'; } signed main() { IOS; int tt = 1; cin >> tt; while (tt--) solve(); return 0; }