AOJ 0540 Amidakuji

  • 概要

日本語の問題なので省略させていただきます。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0540


  • 解法

各横棒の両端に対して上にたどっていった時にたどり着く番号と

下にたどっていった時の得点を先に求めておきます。

そうすることでもしi番目の横棒を取り除くとき、両端の値をswapするだけでいいことがわかります。


さらに考えると消す横棒の両端から上にたどった時の番号がどちらもk以下(選ぶ縦棒)であるとき

その横棒を消して値をswapさせても解は変化しないことがわかります。

なので選ぶ縦棒と選ばれない縦棒のを結んでいる横棒のうち、その差が一番大きくなる横棒が解となります。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<numeric>
#include<map>
#define MAX_N 1000

using namespace std;
typedef pair<int,int> P;
P score[100001],par[100001];

int main()
{
	int n,m,h,k;
	while(scanf("%d%d%d%d",&n,&m,&h,&k),n){
		vector<P> v;
		int p[MAX_N+1],s[MAX_N+1];

		for(int i=0;i<n;i++){
			s[i]=i;
			scanf("%d",&p[i]);
		}
		for(int i=0;i<m;i++){
			int a,b;scanf("%d%d",&a,&b);
			v.push_back(make_pair(b,a-1));
		}
		sort(v.begin(),v.end());

		for(int i=0;i<m;i++){
			int a,b,j=m-i-1;
			par[i].first=s[v[i].second];
			par[i].second=s[v[i].second+1];
			swap(s[v[i].second],s[v[i].second+1]);
			score[j].first=p[v[j].second];
			score[j].second=p[v[j].second+1];
			swap(p[v[j].second],p[v[j].second+1]);
		}

		int sum=accumulate(p,p+k,0);
		int ans=sum;
		for(int i=0;i<m;i++){
			if(par[i].first<k && par[i].second>=k){
				ans=min(sum-(score[i].second-score[i].first),ans);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}