P11069 「QMSOI R1」 生熏鱼题目背景一切起源于一个叫神荀彧的武将…那这道题与神荀彧的关系在哪里呢题目描述一共有n nn种攻击第i ii种攻击会先让你得到a i a_iai​点经验然后让你失去b i b_ibi​点血量。你将依次受到k kk次攻击其中第i ii次攻击的种类是c i c_ici​你的初始血量为m mm。为了获得更多的经验你可以选择n nn种攻击中的任意种并防止你受到的第一次这种攻击防止后既不会损失血量也不会增加经验值。现在你想知道的是在你的血量降到0 00及以下前最多能获得多少点经验。输入格式一行 4 个整数分别代表n , m , k , s n,m,k,sn,m,k,s其中s ss为随机种子其它变量含义与题目描述相同。因为本题输入数据过大选手需要使用如下方式获取数据constintM1e9,C1e55;voidread(){cinnmks;mt19937rand(s);for(inti1;in;i)a[i]rand()%M1,b[i]rand()%C1;for(inti1;ik;i)c[i]rand()%n1;}数组含义与题目描述中相同。输出格式输出一行一个整数表示你最多能获得多少点经验。输入输出样例 #1输入 #12 100000 5 114514输出 #13765807592说明/提示样例解释样例1 11的数据中a { 953888980 , 904140652 } , b { 6583 , 80624 } , c { 1 , 2 , 1 , 1 , 2 } a\{953888980,904140652\},b\{6583,80624\},c\{1,2,1,1,2\}a{953888980,904140652},b{6583,80624},c{1,2,1,1,2}。此时显然可以不防止任何攻击或者防止第一次类型2 22的攻击获得953888980 × 3 904140652 3765807592 953888980\times 39041406523765807592953888980×39041406523765807592的经验值。可以证明不存在获得经验值更多的方案。数据范围本题使用 subtask 进行捆绑测试每个 subtask 的具体分值如下子任务n nnk kk分值0 00≤ 10 \le 10≤10≤ 10 3 \le 10^3≤10320 20201 11≤ 20 \le 20≤20≤ 10 7 \le 10^7≤10730 30302 22≤ 24 \le 24≤24≤ 2 × 10 7 \le 2\times 10^7≤2×10750 5050对于所有数据满足1 ≤ n ≤ 24 1\le n \le 241≤n≤241 ≤ k ≤ 2 × 10 7 1 \le k \le 2\times 10^71≤k≤2×1071 ≤ s , m ≤ 10 9 1\le s,m\le 10^91≤s,m≤109。C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintmaxn30,maxk2e75;constintM1e9,C1e55;intn,m,k,s;inta[maxn],b[maxn],c[maxk];ll dp[C*maxn],suf[C*maxn];boolvis[maxn];// vis[i]表示第i种攻击是否出现过voidsolve(){cinnmks;mt19937rand(s);for(inti1;in;i)a[i]rand()%M1,b[i]rand()%C1;for(inti1;ik;i)c[i]rand()%n1;memset(dp,0x3f,sizeofdp);memset(suf,0x3f,sizeofsuf);dp[0]0;ll sum0,maxn0;// s统计经验前缀和、maxn统计能获得的最大经验for(inti1;ik;i){if(!vis[c[i]]){// 如果这是第c[i]种攻击第一次出现vis[c[i]]1;for(intjC*n;jb[c[i]];j--){// 注意滚动数组要倒着遍历避免提前计算dp[j]min(dp[j],dp[j-b[c[i]]]a[c[i]]);}for(intjC*n;j0;j--){suf[j]min(suf[j1],dp[j]);}}suma[c[i]];if(m0){if(1-mC*nsuf[1-m]!LLONG_MAX){maxnmax(maxn,sum-suf[1-m]);}elsebreak;// 否则说明救不回来了退出循环即可}else{maxnmax(maxn,sum);}m-b[c[i]];}coutmaxn\n;}signedmain(){solve();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容