Codeforces #672 Div2 E. Battle Lemmings

ややこしい設定。
https://codeforces.com/contest/1420/problem/E

問題

01で構成された数列Aが与えられる。
Aのスコアを、以下を満たすindexの対(i,j)の数で定める。

• A[i]=A[j]=0かつA[(i+1)...(j-1)]に1個以上1がある。

Aの隣接要素をw回までスワップできるときのスコアの最大値を、各wについて求めよ。

解法

全体で0がX個、1がY個あるとする。
1で区切られた領域毎に0を挿入することを考える。
dp(x,y,s) := 直前の領域までに0がx個、1がy個あり、その状態に至るのにswapが最小s回必要な場合の最大スコア
とする。
次の領域に、0をk個持ってくるのに必要なswap回数をf(k)とすると
dp(x+k,y+1,s+f(k)) := dp(x,y,s)+x*(X-x)
と状態を更新できる。

int N;
int A[808];
int num[2][81];
vector<int> P[2];
int dp[81][81][3250];
int ma[3250];
int X,Y;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		num[0][i+1]=num[0][i];
		num[1][i+1]=num[1][i];
		P[A[i]].push_back(i);
		num[A[i]][i+1]++;
	}
	X=count(A,A+N,0);
	Y=count(A,A+N,1);
	
	if(X==N||Y==N) {
		FOR(i,N*(N-1)/2+1) cout<<0<<" ";
		cout<<endl;
		return;
	}
	
	FOR(i,81) FOR(j,81) FOR(x,3250) dp[i][j][x]=-1<<30;
	dp[0][0][0]=0;
	for(j=0;j<Y;j++) for(i=0;i<=X;i++) for(k=0;k<=N*(N-1)/2+1;k++) if(dp[i][j][k]>=0) {
		//cout<<i<<j<<k<<" "<<dp[i][j][k]<<endl;
		int fs=0;
		for(int a=0;i+a<X;a++) if(P[0][i+a]<P[1][j]) fs++;
		int cur=0,sum=0;
		for(int a=0;i+a<=X;a++) {
			if(a) {
				while(j+cur<Y&&P[1][j+cur]<P[0][i+a-1]) cur++;
				sum+=cur;
			}
			//cout<<"!"<<i<<" "<<j<<" "<<k<<" "<<a<<" "<<fs<<" "<<sum<<endl;
			if(a<=fs) {
				dp[i+a][j+1][k+fs-a]=max(dp[i+a][j+1][k+fs-a],dp[i][j][k]+i*a);
			}
			else {
				dp[i+a][j+1][k+sum]=max(dp[i+a][j+1][k+sum],dp[i][j][k]+i*a);
			}
		}
		
	}
	//cout<<"###"<<endl;
	
	FOR(i,N*(N-1)/2+1) {
		if(i) ma[i]=ma[i-1];
		for(x=0;x<=X;x++) if(dp[x][Y][i]>=0) {
			//cout<<"!"<<x<<i<<" "<<dp[x][Y][i]<<"->"<<dp[x][Y][i]+x*(X-x)<<endl;
			ma[i]=max(ma[i],dp[x][Y][i]+x*(X-x));
		}
		cout<<ma[i]<<" ";
	}
	cout<<endl;
}

まとめ

落ち着いて考えればそれほど難しくない。
自分も本番中時間に余裕をもって解けているね。