目录

题目：

题目描述：

思路：

分析：

结论：

AC代码：

---

题目：

题目描述：

对于每个案例，先给你三个整数（n，a，b）（需要征服的国家数，征服系数，搬家系数）

再给你 n 个整数代表要征服的国家位置 Xi 

你的首都的起始位置在 0 ，你可以有两种操作：

① 移动你的首都从 c1 到 c2（另一个已被征服的国家位置），花费 a * | c1 - c2 |

② 假设首都在 c1 ，要征服的国家在 c2 ，那么征服这个国家的花费是 b * | c1 - c2 |，注意，你要征服的国家与你的首都之间不能有未征服的国家，并且征服完一个国家之后首都并不会变

请寻找能征服这 n 个国家的最小花费（最后首都在哪里都无所谓）

思路：

题目描述可能有点混乱，简单来说你只有两种操作，你的首都起始位置在 0 ，要么攻打右边第一个未被攻打的国家，要么考虑往右边搬到一个已经攻打了的国家。

所以怎么才能让花费最少？

如果不想听我分析可以直接看结论（可点击）

---

分析：

首先，对于花费来说，其实只有两类，①征服路花费  ②搬家路花费

我们可以用两种颜色的线来表示两类花费

总花费就变成了两种颜色的线段长度分别乘上对应的系数（搬家路系数 a 和征服路系数 b ）

然后，我们先入为主找两个特例尝试一下

特例1：

如果一直不搬家，我们的花费是多少？

此时，总花费就是所有橙色线段的长度和乘上征服系数b，同时我们也发现，如果不搬家，前面路径重叠的部分很多，如果征服路系数 b 特别大， 搬家路系数a 比较小的话，搬家能够有效的减少前面重复路径，达到俭省总费用的目的。

特例2：

如果征服完一个就立刻搬家呢？

很明显，相较于特例1，特例2 减少了很多橙色路径，但相对的，如果搬家路系数 a 非常大，那么有可能特例2 还不如特例1 .....

特例3：

如果我们确定一定要搬到 5 的位置，两种方式的比较（③征服完 3 立刻搬 和 ④征服完 5 再一起搬）

发现，③ 比 ④多出来了一段橙色路径，所以如果确定了要搬到某个位置，立刻搬一定比等征服完几个之后一起搬更节省。如果能确定下来是否搬到某节点，立刻搬首都的决策是无后效性的。

.........

通过特例1 和特例2 ，我们需要对后面的情况预先进行规划，特例3 让我们知道，如果征服了一个地方，我们必须立刻做出判断是否搬首都到此位置，如果不搬那就永远不搬了

那么当我们征服完一个国家之后，如何判断是否搬？如下图

上面是搬，下面是不搬，我们可以看到唯一的区别就是两个黑色框，那我们比较这两个黑框内谁更小即可，然后进行相对的操作

结论：

开两个前缀和，征服前缀和（ precon[ ] ），搬家路前缀和（ premov[ ] ）

从左到右依次遍历每一个要征服的国家，每一次，都征服这个国家，征服过后判断是否要搬到此地

此时假设：

首都位置为 last

征服掉的国家是第 i 个

后面未征服的国家数 temp

c1（不搬）和c2（搬）为两种选择

结合这张图，我们可以知道：

temp = n - i

c1 = temp * ( precon[ i ] - precon[ last ])

c2 = premov[ i ] - premov[ last ]

若 c1 >= c2 说明搬合适，我们更新 last 到当前第 i 个国家的位置，并将搬首都费加到总和内

若 c1 < c2 说明不搬合适，直接去征服下一个国家即可

思路有了，具体操作请看AC代码

AC代码：

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

typedef long long ll;
const int N = 2e5 + 5;

ll x[N];//位置
ll precon[N];//征服费前缀
ll premov[N];//搬家费前缀

void solve()
{
	ll n, a, b;
	ll sum = 0;
	cin >> n >> a >> b;

	for (int i = 1; i <= n; i++)
	{
		cin >> x[i];
		premov[i] = premov[i - 1] + (x[i] - x[i - 1]) * a;
		precon[i] = precon[i - 1] + (x[i] - x[i - 1]) * b;
	}


	ll last = 0;//首都位置
	for (ll i = 1; i <= n; i++)
	{
		sum += precon[i] - precon[last];
		if (i == n)
			break;

		ll temp = n - i;

		ll c1, c2;//两种操作
		c1 = temp * (precon[i] - precon[last]);
		c2 = premov[i] - premov[last];

		if (c1 >= c2)
		{
			sum += c2;
			last = i;
		}
	}
	cout << sum << '\n';
}

int main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--)
		solve();
	return 0;
}