题解：Robot Customize

Robot Customize

题目大意

我们需要将

N

种部件分配到机器人的头部或身体上，使得：

头部总重量不超过身体总重量（防止机器人倒下）;
所有部件的幸福感总和最大化。

而每个部件有三种属性：

重量 $W_i$
连接头部的幸福感 $H_i$
连接身体的幸福感 $B_i$

关键思路

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

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

初始状态：假设所有部件都连接到身体上（因为头轻脚重一定不会摔倒），此时总幸福感为 $\sum_{i=1}^N B_i$ ；
部件移动：如果将一个部件从身体移动到头部：
- 幸福感变化： $H_i - B_i$ （可能为正或负），
- 重量变化：头部增加 $W_i$ ，身体减少 $W_i$ ，
- 净重量影响：头部相对于身体增加了 $2 \times W_i$ ；
约束条件转换：头部重量 $\le$ 身体重量：
- 初始：头部重量 $=0$ ，身体重量 $=$ 总重量 $T = \sum_{i=1}^N W_i$ ，
- 移动一些部件后：头部重量 $=S$ ，身体重量 $=T-S$ ，
- 约束条件： $S \le T - S$ ，则 $2 \times S \le T$ ；
问题本质：选择一部分部件连接到头部，使得：
- 头部总重量 $2 \times S \le T$ ，
- 幸福感增加值 $\sum H_i-B_i$ 最大化。

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

物品：可以移动到头部的部件（仅考虑 $H_i > B_i$ 的部件，因为只有这些移动才会增加幸福感）；
重量： $2 \times W_i$ ；
价值： $H_i - B_i$ ；
背包容量：总重量 $T$ 。

代码详解

CPP

#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;
}

题解：Robot Customize

文章操作

Robot Customize

题目大意

关键思路

代码详解

相关推荐

评论

题解：Robot Customize