标题:[APIO/TSC 2007]データバックアップ

トランスファゲート
IT会社では、大規模なオフィスビルやオフィスビルのコンピュータデータをバックアップしています.しかし、データバックアップの仕事は退屈なので、異なるオフィスビルを互いにバックアップし、家に座ってコンピュータゲームを楽しむシステムを設計したいと思っています.オフィスビルは同じ通りにあることが知られています.あなたはこれらのオフィスビルにペアを組むことにしました(2つのグループ).各オフィスビルは、この2つの建物の間にネットワークケーブルを敷設することで、互いにバックアップすることができます.しかし、ネットワークケーブルの費用は高い.ローカルテレコムはK本のネットワークケーブルしか提供できません.これは、K対オフィスビル(または合計2 Kのオフィスビル)のバックアップのみを手配できることを意味します.いずれのオフィスビルも唯一のペアグループに属している(言い換えれば、この2 Kのオフィスビルはきっと違うに違いない).また、電信会社はネットワークケーブルの長さ(キロ数)で料金を徴収する必要があります.そのため、このK対オフィスビルを選択して、ケーブルの全長をできるだけ短くする必要があります.言い換えれば、このK対のオフィスビルを選択して、各対のオフィスビル間の距離の和(総距離)をできるだけ小さくする必要があります.次の例では、5人のお客様がオフィスビルが1つの街にあると仮定します.下図に示します.この5つのオフィスビルは、通りの起点から1 km、3 km、4 km、6 km、12 kmに位置しています.電信会社はK=2本のケーブルしか提供していません.
実は、この問題の意味は、1組の数に対して差分を行い、k個の数が2つずつ隣接していないことを探し出して選択した数を最小限に抑えるためにまず考えやすいnkのアルゴリズムがあり、DPを行うことですが、ここではスクロールする必要があります.メモリが足りないので、f[i,j]でi番目の点を表すときにj個を選びました.ここで欲張りなやり方を話します.まず、直接欲張りは間違いないに違いない.例えば4、3、5、10、欲張りの結果は13だが、明らかに結果は9であるはずなので、ここの欲張りは後悔している(このような考えはネットの流れに似ているので、これはシミュレーション費用の流れだと言っている大物がいるが、私はemmmではない).どうやって後悔するの?点iを削除するたびに、iと両側の点を削除します.ans+s[i]とは反対にans+s[i-1]+s[i+1]です.だから、iを削除した後にs[i-1]+s[i+1]-s[i]という値の点を加える必要があります.そうすると、両側の点を取ったら、2回加算するとs[i-1]+s[i+1]-s[i]=s[i-1]+s[i+1]となり、両側の点を取ったことになります.これについてのメンテナンスは、スタックを使ってもいいし、バランスツリーを使ってもいい(実はバランスツリーを使ってメンテナンスしやすいと思いますが、あわてて優先キューを打ってしまいました)ACコードは以下の通りです.

#include 
#include 
#include 
#include 
using namespace std;
#define re register
#define gc getchar()
#define ll long long
#define il inline
const int N=100010,lim=(1<<5);
const ll INF=1e9;
il int read() {
	re int x(0),f(1);
	re char ch=gc;
	while(ch<'0'||ch>'9') {
		if(ch=='-') f=-1;
		ch=gc;
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=gc;
	}
	return x*f;
}
struct node {
	long long x,id;
	bool operator < (const node & a) const {
		return x>a.x;
	}
};
priority_queue <node> q;
int n,k,s[N],la[N],ne[N];
bool vis[N];
int main() {
	n=read(),k=read();
	for(int i=1; i<=n; ++i)
		s[i]=read();
	for(int i=1; i<n; ++i) {
		s[i]=s[i+1]-s[i];la[i]=i-1,ne[i]=i+1;
		q.push((node){
			s[i],i
		});
	}
	s[n]=s[0]=INF;
	int num=0;
	long long ans=0;
	for(re int i=1; i<=k; ++i) {
		node a;
		while(vis[q.top().id]&&!q.empty())
			q.pop();
		a=q.top(),q.pop();
		ans+=a.x;
		int l=la[a.id],r=ne[a.id];
		s[a.id]=s[l]+s[r]-s[a.id];
		ne[la[l]]=ne[l],la[ne[l]]=la[l],la[l]=ne[l]=0;
		ne[la[r]]=ne[r],la[ne[r]]=la[r],la[r]=ne[r]=0;
		vis[l]=vis[r]=1;
		q.push((node) {
			s[a.id],a.id
		});
	}
	cout<<ans;
	return 0;
}