首页 > 其他分享 >2024初秋集训——提高组 #28

2024初秋集训——提高组 #28

时间:2024-10-01 23:13:42浏览次数:1  
标签:战斗力 int 28 决斗 2024 MAXN 操作 80 初秋

B. 车轮战

题目描述

你将进行 \(N\) 场决斗。一开始你的战斗力为 \(s\),咒术强度为 \(x\)。每次决斗之前你可以选择:

  • 令 \(s\leftarrow s+x\)。
  • 令 \(x\leftarrow x+1\)。

每次决斗,如果你的 \(s\ge f_i\),则你赢得决斗。求最多能赢多少场决斗。

思路

我们可以发现,你最多会进行 \(80\) 次操作 \(2\),因为如果你当前已经做了 \(80\) 次,那么接下来再做一次操作 \(2\),则会损失至少 \(80\) 的战斗力,那么你又要用 \(80\) 次操作才能弥补回来,而此时战斗力已经至少有 \(80^2=6400>5000\),所以不做这次操作也能达到这么多,已经能够赢得所有的决斗了。

由此,我们就知道至多会输 \(160\) 场,就是先做 \(80\) 次操作 \(2\),再做 \(80\) 次操作 \(1\)。

我们令 \(dp_{i,j,k}\) 表示考虑前 \(i\) 场,当前 \(x=j\),输了 \(k\) 场的最大 \(s\)。

时空复杂度均为 \(O(N\max\{f_i\})\)。

代码

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

const int MAXN = 5001;

int t, n, s, x, a[MAXN], ans, dp[MAXN][81][161];

void Solve() {
  cin >> n >> s >> x;
  ans = 0;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for(int i = 0; i <= n; ++i) {
    for(int j = 0; j <= 75; ++j) {
      for(int k = 0; k <= 140; ++k) {
        dp[i][j][k] = -int(1e9);
      }
    }
  }
  dp[0][0][0] = s;
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j <= 75; ++j) {
      for(int k = 0; k <= 140; ++k) {
        if(dp[i][j][k] < s) {
          continue;
        }
        if(j < 75 && k + (dp[i][j][k] < a[i + 1]) <= 160) {
          dp[i + 1][j + 1][k + (dp[i][j][k] < a[i + 1])] = max(dp[i + 1][j + 1][k + (dp[i][j][k] < a[i + 1])], dp[i][j][k]);
        }
        if(k + (dp[i][j][k] + j + x < a[i + 1]) <= 160) {
          dp[i + 1][j][k + (dp[i][j][k] + j + x < a[i + 1])] = max(dp[i + 1][j][k + (dp[i][j][k] + j + x < a[i + 1])], dp[i][j][k] + j + x);
        }
      }
    }
  }
  for(int i = 0; i <= 160; ++i) {
    for(int j = 0; j <= 75; ++j) {
      if(dp[n][j][i] >= s) {
        cout << n - i << "\n";
        return;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for(cin >> t; t--; Solve()) {
  }
  return 0;
}

标签:战斗力,int,28,决斗,2024,MAXN,操作,80,初秋
From: https://www.cnblogs.com/yaosicheng124/p/18444260

相关文章

  • 2024/09/30 模拟赛总结
    \(0+0+42+40\),T1在写正解的时候突然比赛还有1分钟结束,然后把freopen注释的暴力在最后几秒交了上去#A.博弈唐氏xor-hashing,首先博弈游戏很简单,如果有一个数的出现次数是奇数则先手必胜,否则先手必败那么先手必败的条件就是路径上所有边权都是两两配对的,即异或和为\(0\)。那......
  • 2024.10.1 总结(集训;数据结构 主要是线段树)
    XK又来给我们讲课了。开心!1.Baka'sTrick两种理解:双栈模拟队列。[找到若干个划分点,使得每个区间包含恰好一个划分点。维护划分点到划分点段的前缀、后缀信息。在在线的实现中,在队列中维护仅仅一个划分点,维护它到前面每个点和它到后面每个点的信息。当这个划分点出队时,把队......
  • [20240930]关于共享池-表对象在库缓存探究2.txt
    [20240930]关于共享池-表对象在库缓存探究2.txt--//以前探究过sql语句在共享池存在父子游标,父游标存在堆0,子游标堆0,堆6,通过各种指针链接起来,--//父游标的堆0上保存了所有子游标的列表和各个子游标的句柄指针,子游标的堆6中保存了解析过的执行计划等解析信息。--//前几天测试表对象......
  • 2024/09/29 模拟赛总结
    \(0+0+0+0=0\),感觉不如#include<bits./stdc++.h>#A.你相信()吗\(70\)分的\(O(n^3)\)算法很好解决,枚举出三盏灯的亮度后,剩下一个灯的亮度一定固定。对于每个格子剩余亮度需求取max即可。然后我们充分发扬人类智慧,当\(n\le400\)时跑暴力,否则考虑推式子,下面的\(=\)表......
  • 【牛客训练记录】2024牛客国庆集训派对day1
    https://ac.nowcoder.com/acm/contest/90188#question赛后反思好像没有,全场只做出来一题QAQJ题想在图上找到同色三角形,我们枚举至少是\(O(n^3)\)的,所以我们考虑容斥定理(?),去找异色三角形,因为只要保证一条边上两点颜色不一样,另找一点随便都可以,所以我们只要统计白色的点数,......
  • 当一群人聚在 RTE Open Day 现场|S 创上海 2024 回顾
       散场以后 9月20和21日的上海,RTE开发者社区正在主持第四期RTEOpenDay。这里有两场台风暴雨,和一群并没有因此降低半分热情的RTEbuilders! 这次我们把为实时互动领域的开发者们搭建的线下交流场,放在了一个年轻、多元、活力十足的科技聚会——S创上海202......
  • 28_分布式文档系统_阶段性总结以及什么是distributed document store
    1、阶段性总结1~8讲:快速入门了一下,最基本的原理,最基本的操作9~13讲:在入门之后,对ES的分布式的基本原理,进行了相对深入一些的剖析14~27讲:围绕着document这个东西,进行操作,进行讲解和分析2、什么是distributeddocumentstore到目前为止,你觉得你在学什么东西,给大家一个直观的感觉......
  • 2024.09 做题记录
    20240901上午模拟赛能想出来T2,但是怎么没想出来呢。T2:及时去想\(2^{k/2}\)的做法,猜到是DP套DP,但是没有进一步思考内层状态是\(O(2^{k/2}k)\)的。T3:没调完/fn/fnT4:赛时会了\(f_{i,j}\)表示\(B(i,j)\)是否可行,但是么有去想进一步的单调性优化,\(f_{i}\)可以表示最......
  • CSP2024-30
    A题意:将一个圆等分为\(K\)分,给出其中\(n\)个等分点的编号,\(x_i<x_{i+1}\)。有向边\(i\toj\)存在,当且仅当\(j\)是距离\(i\)最大的点(不唯一),且与图中其他边无交点(端点不算)。求图中最多有多少条边。\(3\leK\le10^9,3\len\le\min(K,10^5)\)。引理:不存在......
  • The 2024 ICPC Asia East Continent Online Contest (II)
    A.GamblingonChoosingRegionals最差情况就是,强队都和你去一起。因此赛站越小,排名也一定越小。然后只要动态实现出每个学校最强的若干只队伍就好了。#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;#defineinti64using......