Codeforces ECR #151 : E. Boxes and Balls

こっちは普通に解けたね。
https://codeforces.com/contest/1845/problem/E

問題

N要素のバイナリ配列Aが与えられる。
隣接する0と1をK回swapするとき、得られるAは何通りか。

解法

n回で到達できる状態は、n+2回でも到達できる。
そこで、最短K-2n回で到達できる状態を数え上げよう。

f(n,m,k) := Aの先頭n要素まで見たとき、最後の0がm番目の1の手前にあるような状態で、swap回数が最小K回である並び順
としてnの小さい順にDPしていく。

int N,K;
int A[1515];
const int mo=1000000007;

int from[1515][1515];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	int tn1=0;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]) tn1++;
	}
	int n1=0;
	from[0][0]=1;
	FOR(i,N) {
		if(A[i]==0) {
			for(k=K;k>=0;k--) {
				int sum=0;
				for(j=0;j<=tn1;j++) {
					if(from[j][k]) {
						sum+=from[j][k];
						if(sum>=mo) sum-=mo;
						from[j][k]=0;
					}
					if(k+abs(n1-j)<=K) from[j][k+abs(n1-j)]=sum;
				}
			}
		}
		else {
			n1++;
		}
		
	}
	ll ret=0;
	FOR(i,tn1+1) {
		for(j=K%2;j<=K;j+=2) ret+=from[i][j];
	}
	cout<<ret%mo<<endl;
	
	
}

まとめ

最後のコードは短いけど、結構手間取ってるな…。