P1489 猫狗大战【洛谷算法习题】

P1489 猫狗大战网页链接P1489 猫狗大战题目描述新一年度的猫狗大战通过 SC星际争霸这款经典的游戏来较量野猫和飞狗这对冤家为此已经准备好久了为了使战争更有难度和戏剧性双方约定只能选择 Terran人族并且只能造机枪兵。比赛开始了很快野猫已经攒足几队机枪兵试探性的发动进攻然而飞狗的机枪兵个数也已经不少了。野猫和飞狗的兵在飞狗的家门口相遇了于是便有一场腥风血雨和阵阵惨叫声。由于是在飞狗的家门口飞狗的兵补给会很快野猫看敌不过决定撤退。这时飞狗的兵力也不足够多所以没追出来。由于不允许造医生机枪兵没办法补血。受伤的兵只好忍了。现在野猫又攒足了足够的兵力决定发起第二次进攻。为了使这次进攻给狗狗造成更大的打击野猫决定把现有的兵分成两部分从两路进攻。由于有些兵在第一次战斗中受伤了为了使两部分的兵实力平均些分的规则是这样的两部分兵的个数最多只能差一个每部分兵的血值总和必须要尽可能接近。现在请你编写一个程序给定野猫现在有的兵的个数以及每个兵的血格值求出野猫按上述规则分成两部分后每部分兵的血值总和。输入格式第一行为一个整数n ( 1 ≤ n ≤ 200 ) n\ (1 \le n \le 200)n(1≤n≤200)表示野猫现在有的机枪兵的个数。以下的n nn行每行一个整数表示每个机枪兵的血格( 1 ≤ a i ≤ 40 ) (1 \le a_i \le 40)(1≤ai​≤40)。输出格式一行为两个整数表示分成两部分后每部分兵的血值总和。要求输出的第一部分兵的血量总和不大于第二部分兵的血量总和。输入输出样例 #1输入 #13 35 20 32输出 #135 52说明/提示TO 狗狗这道题的数据范围我已经尽量按星际的游戏规则来了如果你再固执于由于机枪兵的攻击力一定使不能达到某些血格值或者游戏中一定要造农民不能使机枪兵的人数达到200 200200的话我只能决定将那场猫狗大战的录像公开于世人了解题思路本题是0/1 背包 分组均衡的经典题型。要求将n nn个兵分成两组使得两组人数最多差一个并且两组血量总和尽可能接近。可以将问题转化为从n nn个数中选出恰好⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋个数使其和尽可能接近总和的一半。1. 问题等价转化两组人数最多差一个即一组人数为⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋另一组为n − ⌊ n / 2 ⌋ n - \lfloor n/2 \rfloorn−⌊n/2⌋当n nn为奇数时差1 11。设总血量为t o t a l totaltotal若选出的⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋个兵的血量和为S SS则另一组的血量和为t o t a l − S total - Stotal−S。为了使两部分血量和尽可能接近只需让S SS尽可能接近t o t a l / 2 total/2total/2。因此问题转化为在n nn个数中选出恰好k ⌊ n / 2 ⌋ k \lfloor n/2 \rfloork⌊n/2⌋个数求能组成的最接近t o t a l / 2 total/2total/2的和。2. 算法实现二维 0/1 背包状态定义dp[i][j]表示从前若干个兵中选出恰好i ii个能否组成血量和j jj1表示能0表示不能。初始化dp[0][0] 1其余为0。转移方程对于每个兵的血量a k a_kak​逆序更新数量i ii和血量j jjdp[i][j] | dp[i-1][j-a[k]]即如果不选当前兵则状态不变如果选则从前i − 1 i-1i−1个、血量和j − a [ k ] j-a[k]j−a[k]的状态转移过来。容量与数量上限i ii最大枚举到k ⌊ n / 2 ⌋ k \lfloor n/2 \rfloork⌊n/2⌋血量总和最大为200 × 40 8000 200 \times 40 8000200×408000。寻找最优解遍历所有可能的血量和j jj若dp[k][j]为真计算两组血量差∣ 2 j − t o t a l ∣ |2j - total|∣2j−total∣取差值最小的j jj作为答案。输出按题目要求先输出较小的血量和再输出较大的血量和。3. 复杂度分析时间复杂度背包三层循环兵数n ≤ 200 n \le 200n≤200血量上限8000 80008000数量上限k ≤ 100 k \le 100k≤100总操作量约200 × 100 × 8000 ≈ 1.6 × 10 8 200 \times 100 \times 8000 \approx 1.6 \times 10^8200×100×8000≈1.6×108在可接受范围内使用布尔位运算可优化常数。空间复杂度O ( k × maxSum ) ≈ 100 × 8000 O(k \times \text{maxSum}) \approx 100 \times 8000O(k×maxSum)≈100×8000完全可行。总结将人数和血量双重约束转化为二维 0/1 背包求解恰好选出k kk个数时最接近总和一半的血量和。最后根据最优S SS输出两组的血量和。该方法直观且数据范围下效率足够。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;ll a[205];ll dp[205][8005];ll total;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i){cina[i];totala[i];}dp[0][0]1;for(ll k1;kn;k){for(ll in/21;i1;i--){for(ll j8000;ja[k];j--){dp[i][j](dp[i][j]|dp[i-1][j-a[k]]);}}}ll ans0;ll diffINF;for(ll j0;j8000;j){if(dp[n/2][j]){ll curllabs(2*j-total);if(curdiff){diffcur;ansj;}}}coutmin(ans,total-ans) max(ans,total-ans)endl;return0;}