首页 > 小美打怪

kilomatutinal

发表于 2026-01-05 02:50:02

其实这道题的核心就是找出小美能连续打败的怪物最长严格递增序列啦！我们可以用动态规划(dp)来一步步解决哦~用排序准备喵~先把所有怪物按照生命力从小到大排序，如果生命力相同，就按攻击力从小到大排。小科普喵：vector<pair<int,int>>如果用sort函数就是以fir 展开全文

以诚丶

发表于 2025-06-08 20:26:03

经典题目：最长递增子序列的变种。我们先将满足所有小于和的放到一个数组中，然后按照第一维度降序排序，如果相等，那么升序排序。然后找出第二维的最长递减子序列就是我们的答案。为什么需要相等的时候升序排序呢？因为题目要求了相等的不能够杀死，那么我们给他升序，那么找最长递减的时候就不可能选到。这道展开全文

我是签到糕手

发表于 2024-06-25 00:17:34

这题仔细想想其实是板子题。n为1000想到可以暴力枚举。于是可以考虑令dp[i]为到i时的最大打怪数。则dp[i]=max(dp[j]+1,dp[i])这里有点转化的思维。从代码上看是小的吃大的，但其实我们可以通过判断如果能吃大的，那么小到大和大到小就没有顺序差别。 #inclu 展开全文

周康禧

发表于 2026-01-05 19:58:26

因为n的范围比较小，可以直接暴力n^2算一下，在排序之后，算一下以第i个为结尾的最多可以击败的怪物数量 void solve(){ int n,H,A; cin>>n>>H>>A; vector<pair<int,int> 展开全文

quchen666

发表于 2026-01-05 13:37:47

#include <bits/stdc++.h> using namespace std; const int N = 3e5+10; struct Node { int a,h; }nd[N]; int dp[N]; bool cmp(Node a,Node b) { 展开全文

xiaowang5242

发表于 2026-01-05 13:38:09

void solve() { int n, h0, a0; rd(n, h0, a0); vector<int> h(n + 1), a(n + 1); rep(i, 1, n) rd(h[i]); rep(i, 1, n) rd(a[i]); 展开全文

软件25_4刘卓生

发表于 2026-01-05 14:22:59

#include <bits/stdc++.h> using namespace std; int mei_0,mei_1;//小美的生命值和攻击力 bool cmp(const pair<int,int>& a,const pair<int,int>& 展开全文

Vermouth贝尔摩德

发表于 2026-01-05 16:27:35

#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { int n, h, a; while (cin >&g 展开全文

fruian

发表于 2026-01-05 20:13:02

图论解法复杂度为 , 并不会比常规的最长上升子序列做法更优, 但是思路可以了解一下已知, 若 h[i] > h[j] && a[i] > a[j], 那么节点 j 的答案一定至少为节点 i 的答案 +1, 用 dp 转移方程可以表示为 dp[j] = max(dp[ 展开全文

ATRI_execution

发表于 2026-01-05 11:39:16

# 堆叠问题 # 先按血量降序排序，然后按攻击力降序排序，相同血量按攻击力升序排序，这样就只用计算攻击力的最长降序子序列了 import sys import bisect def solve(): n, H, A = map(int, input().split()) data 展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛