题解：Robot Customize

· · 题解

Robot Customize

题目大意

我们需要将 N 种部件分配到机器人的头部或身体上，使得：

而每个部件有三种属性：

关键思路

初看这个问题，我会立马想到贪心策略，比如按某种优先级排序后分配部件。但仔细分析会发现，部件的重量和幸福感之间没有简单的单调关系，贪心法无法保证最优解。

我们可以这样重新思考问题：

  1. 初始状态：假设所有部件都连接到身体上（因为头轻脚重一定不会摔倒），此时总幸福感为 \sum_{i=1}^N B_i；

  2. 部件移动：如果将一个部件从身体移动到头部：

    • 幸福感变化：H_i - B_i（可能为正或负），
    • 重量变化：头部增加 W_i，身体减少 W_i，
    • 净重量影响：头部相对于身体增加了 2 \times W_i；

  3. 约束条件转换：头部重量 \le 身体重量：

    • 初始：头部重量 =0，身体重量 = 总重量 T = \sum_{i=1}^N W_i，
    • 移动一些部件后：头部重量 =S，身体重量 =T-S，
    • 约束条件：S \le T - S，则 2 \times S \le T；

  4. 问题本质：选择一部分部件连接到头部，使得：

    • 头部总重量 2 \times S \le T，
    • 幸福感增加值 \sum H_i-B_i 最大化。

看到这，相信大家都懂了：这正好是一个 01 背包问题：

代码详解

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,w[505],v[505],len,t,now,lst,ans;
unordered_map<int,int> dp[5]; //使用unordered_map优化时间，再开一个滚动数组，只存储可能的状态（不然要TLE）
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int nw,nh,nb;
        cin>>nw>>nh>>nb;
        t+=nw；//计算总重量
        ans+=nb; //初始状态：所有部件都连身体
        //只考虑那些连接到头部能增加幸福感的部件
        if(nh>nb){
            len++;
            w[len]=nw*2; //移动部件到头部会使头部相对重量增加 2*Wi
            v[len]=nh-nb; //移动部件到头部带来的幸福感增加值
        }
    }
    //直接跑一次0-1背包模板即可
    for(int i=1;i<=len;i++){
        //滚动数组优化：交替使用两个unordered_map
        if(i%2==0) now=2,lst=1;
        else now=1,lst=2;
        for(int j=1;j<=t;j++){
            if(j<w[i]) dp[now][j]=dp[lst][j];
            else dp[now][j]=max(dp[lst][j],dp[lst][j-w[i]]+v[i]);
        }       
    }
    ans+=dp[now][t]; //最终结果 = 初始幸福感 + 通过移动部件能增加的最大幸福感
    cout<<ans;
    return 0;
}