AtCoder ABC #328 (トヨタ自動車プログラミングコンテスト2023#7) : G - Cut and Reorder

Fまで順調なのでGで謎はまり…。
https://atcoder.jp/contests/abc328/tasks/abc328_g

問題

N要素の整数列A,Bが与えられる。
Aに以下の処理を繰り返し、AをBと一致させたい。

• AをX個の連続部分列に分割し、このX個を任意の順に並べ替える。この際コストは(X-1)Cかかる。
• Aの1要素を選び1増減させる。この際コストは1かかる。

最小コストを求めよ。

解法

Aを並べ替えて、先頭から詰めていくことを考える。
これは確定済みの要素のbitmaskと末尾の要素を持ったBitDPができるが、生憎メモリがO(N*2^N)、処理時間がO(N^2*2^N)かかりどちらも上限を超える。

そこでメモリ使用量と処理時間を削減することを考える。
末尾の要素を覚えるのをやめ、BitDPの過程では、Aで元々連続していた要素をまとめて先頭に詰めていこう。
これでメモリ消費をO(2^N)に抑えられる。また、処理時間も均しでO(N*2^N)になる。

int N;
ll C;
ll A[22],B[22];

ll dp[1<<22];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	
	int mask;
	FOR(mask,1<<N) dp[mask]=1LL<<60;
	dp[0]=-C;
	FOR(mask,1<<N) {
		x=__builtin_popcount(mask);
		FOR(i,N) {
			ll sum=dp[mask]+C;
			int nmask=mask;
			for(j=i;j<N;j++) {
				if(mask&(1<<j)) break;
				nmask|=1<<j;
				sum+=abs(B[x+(j-i)]-A[j]);
				chmin(dp[nmask],sum);
			}
		}
	}
	cout<<dp[(1<<N)-1]<<endl;
	
}

まとめ

これ何を問いたい問題だったんだろ。メモリ消費に気をつけろ？