广智正解相似但没过

一开始没有使用正解的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;
}

全部评论
确实,我也类似,正向dp,只过了50% import java.util.Scanner; public class Main{ public static int a; public static int b; public static int c; public static int d; public static int[] k; public static Scanner cin = new Scanner(System.in); public static void main(String[] args) { solve(); } public static void solve(){ int t = cin.nextInt(); for(int i=0;i<t;i++) { int h = cin.nextInt();  a = cin.nextInt();  b = cin.nextInt();  c = cin.nextInt();  d  = cin.nextInt();  k = new int[h+1];  int [] ans = new int[h+1]; for(int j=1;j<=h;j++) k[j]=cin.nextInt(); for(int p=1;p<=h;p++) { ans[p]=Math.min(ans[Math.max(p-b, 0)]+a, ans[Math.max(p-d, 0)]+c); if(p-4*b>0) { ans[p]=Math.min(ans[p], ans[Math.max(p-4*b-d-k[p-4*b], 0)]+4*a+c); } } System.out.println(ans[h]); } } }
点赞 回复 分享
发布于 2024-10-21 10:44 河南

相关推荐

积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
07-15 12:24
重庆大学 运营
坏消息:和好工作擦肩而过
给点吧求求了:怎么可能因为差几秒,估计就是简历更好看婉拒了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务