Codeforces ECR #148 : F. Zombies

問題文の理解に手間取るな。
https://codeforces.com/contest/1832/problem/F

問題

N個の入り口から、X分の間、1分あたり1体のペースでゾンビが襲ってくるゲームがある。

N個の入り口の守り方は以下の2通りである。

• i番の入り口には、時刻[L[i],R[i])の間ゾンビを防いでくれる人がいる。
• 入口に電気フェンスを設置する

電気フェンスは計K個ある。
1つのフェンスで複数の入り口を守ることができるが、1つの入り口に複数フェンスを置くことはできない。
また、各フェンスは時間Mの間しかゾンビを防いでくれない。

できるだけ多くのゾンビに襲わせるようにフェンスを置くと、計何体のゾンビを防げないようにできるか。

解法

人とフェンスの稼働時間の共通部分を最大化すればよい。
この時、L[i]+R[i]が近い人は同じフェンスで守るのが効率が良い。

あとは、
dp(n,m) := 先頭n人をm個のフェンスで守るとき、共通部分の最大値
とし、分割統治法の要領で求めて行こう。

ll N,K,X,M;
ll L[2020],R[2020];
ll A[2020],B[2020];
vector<pair<ll,ll>> V;
ll len[4040][2020];
int opt[2020][2020];
ll le[4040][2020];

ll from[2020][2020];
ll val[2020][2020];

void dfs(int cur,int KL,int KR,int FL,int FR) {
	if(KL+1>=KR) return;
	int i;
	if(FL==FR) {
		for(i=KL+1;i<KR;i++) {
			from[i][cur]=FL;
			val[i][cur]=val[i-1][FL]+le[FL][cur];
		}
	}
	else {
		int KM=(KL+KR)/2;
		for(i=FL;i<=FR;i++) {
			if(chmin(val[KM][cur],val[KM-1][i]+le[i][cur])) from[KM][cur]=i;
		}
		dfs(cur,KL,KM,FL,from[KM][cur]);
		dfs(cur,KM,KR,from[KM][cur],FR);
		
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>X>>M;
	vector<ll> cand={0,X-M};
	FOR(i,N) {
		cin>>A[i]>>B[i];
		V.push_back({A[i]+B[i],i});
		cand.push_back(min(A[i],X-M));
		cand.push_back(max(0LL,B[i]-M));
	}
	
	sort(ALL(V));
	FOR(i,N) L[i]=A[V[i].second], R[i]=B[V[i].second];
	
	sort(ALL(cand));
	
	le[0][N]=1LL<<60;
	FOR(i,cand.size()) {
		FOR(j,N) {
			ll x;
			if(cand[i]>=R[j]) {
				x=M+R[j]-L[j];
			}
			else if(cand[i]+M<=L[j]) {
				x=M+R[j]-L[j];
			}
			else {
				x=max(R[j],cand[i]+M)-min(L[j],cand[i]);
			}
			len[i][j+1]=len[i][j]+x;
		}
		if(chmin(le[0][N],len[i][N])) opt[0][N]=i;
	}
	for(l=N-1;l>=1;l--) {
		for(int s=0;s+l<=N;s++) {
			int t=s+l;
			le[s][t]=1LL<<60;
			for(i=((s)?opt[s-1][t]:0);i<=((t<N)?opt[s][t+1]:cand.size()-1);i++) {
				if(chmin(le[s][t],len[i][t]-len[i][s])) opt[s][t]=i;
			}
		}
	}
	
	FOR(i,N+1) FOR(j,N+1) val[j][i]=1LL<<60;
	val[0][0]=0;
	
	for(i=1;i<=N;i++) {
		k=min(i,(int)K);
		FOR(j,i) if(chmin(val[k][i],val[k-1][j]+le[j][i])) from[k][i]=j;
		from[1][i]=0;
		val[1][i]=le[0][i];
		dfs(i,1,k,0,from[k][i]);
	}
	
	
	cout<<1LL*N*X-val[K][N]<<endl;
	
}

まとめ

このDPテク、いつも忘れる。