题解：P12988 [GCJ 2022 #1B] Controlled Inflation

原题链接

• 洛谷 P12988 [GCJ 2022 #1B] Controlled Inflation

题意简述

你需要控制充气泵的气压，依次为 $n$ 位顾客的产品充气，每位顾客有 $p$ 个产品，目标是最小化按钮按压次数。

泵的初始气压为 $0$，每次可调整 $\pm 1$，每位顾客内部的产品顺序可自由选择，但顾客的整体顺序不能改变。

解题思路

顾客优化

设第 $i$ 位顾客的产品最大气压为 $a_i$，最小气压为 $b_i$。

显然，无论以什么顺序处理，气压一定需要覆盖 $a_i$ 和 $b_i$ 这两个极值，其余产品的气压都会被经过。

因此，只需要考虑最大和最小两个极值。

状态设计

对于每位顾客的极值气压，有两种方案：$a_i\to b_i$ 和 $b_i\to a_i$。

这两种方案的内部代价都是 $a_i-b_i$，区别仅在于进入和离开时的位置。

设前 $i$ 位顾客处理完后，停在 $b_i$ 的最小代价为 $f_{i,0}$，停在 $a_i$ 的最小代价为 $f_{i,1}$。

状态转移

若停留在 $b_i$，先从上一位顾客的终态到达 $a_i$，再内部降到 $b_i$：

$$f_{i,0}=a_i-b_i+\min\left(f_{i-1,0}+|b_{i-1}-a_i|,f_{i-1,1}+|a_{i-1}-a_i|\right)$$

若停留在 $a_i$，先到 $b_i$，再升到 $a_i$：

$$f_{i,1}=a_i-b_i+\min\left(f_{i-1,0}+|b_{i-1}-b_i|,f_{i-1,1}+|a_{i-1}-b_i|\right)$$

特别地，对于第一位顾客，可以令：

$$f_{1,0}=f_{1,1}=a_0=b_0=0$$

最终答案为最后一位顾客的两种方案的最小值，即：

$$\min(f_{n,0},f_{n,1})$$

滚动数组

由于状态仅与上一位顾客相关，可使用滚动数组优化，将空间复杂度降至 $O(1)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
ll f[2][2];
int mx[2],mn[2];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    for(int $=1;$<=T;$++)
    {
    	int n,p;
    	cin>>n>>p;
    	f[0][0]=f[0][1]=mx[0]=mn[0]=0;
    	for(int i=1;i<=n;i++)
    	{
    		mx[i&1]=0;mn[i&1]=inf;
    		for(int j=1;j<=p;j++)
    		{
    			int x;
    			cin>>x;
    			mx[i&1]=max(mx[i&1],x);
    			mn[i&1]=min(mn[i&1],x);
    		}
    		f[i&1][0]=mx[i&1]-mn[i&1]+min(
    			f[i&1^1][0]+abs(mn[i&1^1]-mx[i&1]),
    			f[i&1^1][1]+abs(mx[i&1^1]-mx[i&1])
    		);
			f[i&1][1]=mx[i&1]-mn[i&1]+min(
				f[i&1^1][0]+abs(mn[i&1^1]-mn[i&1]),
				f[i&1^1][1]+abs(mx[i&1^1]-mn[i&1])
			);
    	}
    	cout<<"Case #"<<$<<": "<<min(f[n&1][0],f[n&1][1])<<'\n';
    }
    return 0;
}