题目链接:

https://codeforces.com/contest/1197/problem/C

题目大概意思是,给出一个不下降序列,定义cost是区间右端点的值减去区间左端点的值。

要求把数组分为n段,求最小的cost。

今下午训练的时候做到这道题我有点懵(毕竟我是菜鸡),然后就观察了一下,发现了一个小现象。把给出的数组的前后两个元素分别相减,就会得到一个新的数组。这个新数组的各个元素之和,就是某一段区间的cost。

然后我大概连蒙带猜地,写了一段代码来解决这个问题。

我最初的思路大概就是分成n段的话,那么把后面k-1个元素各成为一个数组,然后剩下的成为一个数组。

可是!

这样子很明显是错的。举几个例子就知道这样子做是有问题的。所以,这样的代码在第四个测试点就过不了了。那怎么办呢?

当然是换一题来做啦!放弃这题!

所以训练的时候我没有做出这道题,那到底怎么搞?

其实,这道题的思路就是利用前后两个元素相减得到的新数组,也就是差分数组(我训练完上网查了才知道的)差分数组描述了整个序列的变化情况。

开始分析:

当数组只有一段的时候,总的cost就是差分数组的元素和。

当数组分成两段的时候,在分界线处的那个差分元素就可以消掉了。因为,前后两个元素已经分别属于不同的数组了。那么在这里就不需要计算cost了。这个时候,总的cost就要减去这一小段的cost。

当分为更多段的时候,还是一样,只要多出一个分界线,那么就要减去这个分界线处的cost。

于是,问题就转换成了,当把序列分成k段的时候,如何减掉最多的cost。

分成k段,就是形成k-1个分割线,也就是减去k-1个cost。

我们只需要减去最大的k-1个cost,就能得到最小的cost。

代码如下:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int>m;
int num[300005];

int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0;i <n;i++)
	{
		cin >> num[i];
	}
	for (int i = 1; i < n; i++)
		m.push_back(num[i] - num[i - 1]);
	int cost = 0;
	sort(m.begin(),m.end());

	cost = num[n-1] - num[0];
	
	for (int i =n-2;i>=n-k;i--)
		cost -= m[i];
	cout << cost << endl;
}

欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注