「aoj2411～2420」の編集履歴（バックアップ）一覧に戻る

aoj2411～2420 - (2012/08/01 (水) 20:15:55) のソース

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415
この問題はかなり難しい。
グラフとして見ると一千六百万本の辺をもつグラフみたいなものだな。
どう格闘しても計算量が落ちないのでとりあえず重さが均等に二分割になるように切っていけば近似解を出せると考えて試作品コードを書いたところで力尽きた。
どうやって解こうかな？


#include<stdio.h>
#include<algorithm>
#include<set>

#define lli long long int
struct B{
	lli w;
	int p;
	bool operator<(const B& b)const{
		return w<b.w;
	}
};

std::set<B> memo;
lli sums[4002],ans;

lli saiki(int down,int up,lli herf){
	if(down+1>=up)return sums[up]-sums[down];
	B b;
	b.w=herf;
	std::set<B>::iterator it=memo.lower_bound(b);
	int p1=(*it).p;
	lli w1=(*it).w;
	lli wR=sums[up]-sums[p1-(herf!=w1)];//右側
	lli wL=sums[p1]-sums[down];//左側
	lli re=0;
	if(wL<wR){
		re=saiki(down,p1,wL/2+sums[down]);
		re+=saiki(p1,up,wR/2+sums[p1]);
	}else{
		re= saiki(p1-(herf!=w1),up,wR/2+sums[p1-(herf!=w1)]);
		re+=saiki(down,p1-(herf!=w1),wL/2+sums[down]);
	}
	ans+=re;
	return re;
}


int main(){
	int n;
	lli w;
	std::set<B> body;
	B b;
	b.w=0;
	b.p=0;
	scanf("%d",&n);
	//memo.insert(b);//0番の番兵
	for(int i=1;i<=n;i++){
		scanf("%lld",&w);
		b.p=i;
		b.w+=w;
		sums[i]=b.w;
		memo.insert(b);
	}
	ans=0;
	saiki(0,n,sums[n]/2);
	printf("%lld\n",ans);
}