龍進题目链接：
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;
}欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~
