小红的双生英雄【牛客tracker 每日一题】

小红的双生英雄时间限制1秒 空间限制256M知识点动态规划网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红有n nn个英雄第i ii个英雄的c o s t costcost是a i a_iai​战斗力为b i b_ibi​。另外存在一些“双生英雄”关系如果同时上阵某一对英雄则可以获得额外的战斗力收益。现在小红最多可以上阵四名英雄且要求总c o s t costcost不超过C CC。小红希望你求出组队的最大战斗力。输入描述第一行输入三个整数n , C , m ( 1 ≦ n , C ≦ 10 3 ; 0 ≦ m ≦ n / 2 ) n,C,m(1≦n,C≦10^3; 0≦m≦n/2)n,C,m(1≦n,C≦103;0≦m≦n/2)代表英雄数量、总c o s t costcost限制、双生英雄的对儿数。此后n nn行第i ii行输入两个正整数a i , b i ( 1 ≦ a i , b i ≦ 10 9 ) a_i,b_i(1≦a_i,b_i≦10^9)ai​,bi​(1≦ai​,bi​≦109)代表第i ii个英雄的c o s t costcost和战斗力。此后m mm行第i ii行输入三个正整数u i , v i , w i ( 1 ≦ u i , v i ≦ n ; u i ≠ v i ; 1 ≦ w i ≦ 10 9 ) u_i,v_i,w_i(1≦u_i,v_i≦n;u_i≠v_i;1≦w_i≦10^9)ui​,vi​,wi​(1≦ui​,vi​≦n;ui​vi​;1≦wi​≦109)代表第u i u_iui​和第v i v_ivi​个英雄是双生英雄同时上阵可以额外增加w i w_iwi​战斗力。除此之外保证每个英雄最多只存在一对双生英雄关系。对于40 % 40\%40%的用例额外保证m 0 m0m0。输出描述输出一个整数代表组队的最大战斗力。示例1输入4 10 1 3 9 4 10 6 15 8 20 1 2 15输出34说明在这个样例中小红可以选择上阵第一、二个英雄获得9 10 15 34 91015349101534的战斗力。我们可以证明这是符合要求的最大战斗力。示例2输入4 1 1 3 9 4 10 6 15 8 20 1 2 15输出0解题思路本题是带人数上限的01背包拓展问题核心约束为最多选取4名英雄、总花费不超过C且双生英雄同时上阵可获得额外战斗力加成。利用人数上限极小的特性采用二维动态规划即可高效求解。1. 状态定义定义二维DP数组dp[p][j]表示选取恰好p名英雄、总花费不超过j时能获得的最大战斗力。p的取值范围为 0~4对应上阵0到4名英雄。j的取值范围为 0~C对应总花费上限。初始状态全为0对应选取0名英雄时战斗力为0的基准情况。2. 双生英雄分组处理题目保证每个英雄最多属于一个双生对因此可以将每对双生英雄作为一个独立处理单元读入双生关系时统一交换为u v仅在编号较小的英雄处记录搭档与加成保证每对双生英雄仅被处理一次避免重复计算加成。处理双生对时同时枚举三种选择只选第一个英雄、只选第二个英雄、同时选两个英雄并加上额外加成。3. 状态转移采用倒序枚举的01背包方式保证每个英雄/每对英雄仅被选取一次普通英雄从人数4到1倒序、花费C到英雄cost倒序遍历转移方程为d p [ p ] [ j ] max ⁡ ( d p [ p ] [ j ] , d p [ p − 1 ] [ j − c o s t i ] f i g h t i ) dp[p][j] \max(dp[p][j],\ dp[p-1][j-cost_i] fight_i)dp[p][j]max(dp[p][j],dp[p−1][j−costi​]fighti​)双生英雄对除上述两个单独选取的转移外额外增加双人同选转移需人数≥2d p [ p ] [ j ] max ⁡ ( d p [ p ] [ j ] , d p [ p − 2 ] [ j − c o s t u − c o s t v ] f i g h t u f i g h t v b o n u s ) dp[p][j] \max(dp[p][j],\ dp[p-2][j-cost_u-cost_v] fight_u fight_v bonus)dp[p][j]max(dp[p][j],dp[p−2][j−costu​−costv​]fightu​fightv​bonus)4. 结果统计遍历 0~4 所有人数维度取花费为C时的最大战斗力值即为最终答案。若所有英雄均无法选取结果自然为0符合上阵0人的边界情况。算法总时间复杂度为O ( 4 × n × C ) O(4 \times n \times C)O(4×n×C)n和C均为1000级别时总运算量约400万完全适配1秒时间限制。总结核心逻辑将上阵人数作为DP第二维把双生英雄对合并为一个处理单元通过倒序枚举的01背包转移求解花费与人数双重约束下的最大战斗力。关键操作双生对单次处理防重复加成、人数花费二维倒序转移、人数上限极小化大幅压缩状态规模。效率保障人数维度仅5种状态总状态量可控百万级运算量可毫秒级完成。代码简要说明数据存储cst、ft数组分别存储每个英雄的花费和基础战斗力。con数组记录每个英雄的双生搭档编号uft数组记录对应双生对的额外加成读入时交换u、v保证uv仅在u位置存储搭档信息确保每对只处理一次。DP数组初始化dp[5][1005]二维数组第一维对应选取人数0~4第二维对应花费上限初始全为0对应零人选时战斗力为0的基准状态。逐英雄递推普通英雄无双生搭档倒序遍历人数和花费执行标准01背包转移更新选取当前英雄后的最大战斗力。双生对首个英雄搭档编号更大倒序遍历人数和花费分别更新只选当前英雄、只选搭档、同时选两人加额外加成三种转移。结果输出遍历0~4所有人数字维度取花费上限处的最大值作为最终答案输出。输入优化关闭流同步并解绑tie提升千级数据量下的读取效率所有变量采用long long类型避免数值溢出。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,cap,m;cinncapm;ll cst[1005]{},ft[1005]{},con[1005]{},uft[1005]{};for(ll i1;in;i)cincst[i]ft[i];for(ll i1;im;i){ll u,v,w;cinuvw;if(uv)swap(u,v);con[u]v;uft[u]w;}ll dp[5][1005]{};for(ll i1;in;i){ll kcon[i];for(ll p4;p0;p--){if(k0){for(ll jcap;jcst[i];j--)dp[p][j]max(dp[p][j],dp[p-1][j-cst[i]]ft[i]);}elseif(ki){ll lbmin(cst[i],cst[k]);for(ll jcap;jlb;j--){if(j-cst[i]0)dp[p][j]max(dp[p][j],dp[p-1][j-cst[i]]ft[i]);if(j-cst[k]0)dp[p][j]max(dp[p][j],dp[p-1][j-cst[k]]ft[k]);if(j-cst[i]-cst[k]0p2)dp[p][j]max(dp[p][j],dp[p-2][j-cst[i]-cst[k]]ft[i]ft[k]uft[i]);}}}}ll ans0;for(ll i0;i5;i)if(ansdp[i][cap])ansdp[i][cap];coutans;return0;}