yukicoder : No.1284 Flip Game

今日はちょっと易しめの回。
https://yukicoder.me/problems/no/1284

問題

N枚のカードが並んでおり、各カード片面が赤で片面が白である。初期状態で全カード赤である。
2名で以下のような手順を行う。

• 最初、先手が任意のカードを1枚裏返す。
• 以後、以下の手順を繰り返す
  • 先手は赤いカードのうち任意のカードを1枚裏返す。その時、前回裏返したカードと今回裏返したカードにより、入力で与えられたコストがかかる。
  • その後、後手は先手が1つ前の手番で裏返したカードを、再度裏返してもとに戻す。ただしこの手順は各カード1回しか行えず、2回目は行わない（後手は何もせず終了）
  • 先手の手番でカードがすべて白くなし、後手がそれを戻せないならそこで終了

先手が最適な順でカードをめくるとき、総コストの最小値を求めよ。

解法

(各カードの赤白、各カード後手が戻したことがあるか、1つ前のターンで選んだカード)を状態としてDPしていく。
各カードの状態を3通りにとってO(3^N*N)にもできるが、Nが小さいので横着してO(4^N*N)でも間に合う。

int N;
int C[10][10];

ll dp[1024][1024][11];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) FOR(x,N) cin>>C[y][x];
	
	FOR(x,1024) FOR(y,1024) FOR(r,10) dp[x][y][r]=1LL<<60;
	FOR(r,N) dp[1<<r][0][r]=0;
	int m1,m2;
	ll ret=1LL<<60;
	FOR(m2,1<<N) FOR(m1,1<<N) FOR(x,N) if(dp[m1][m2][x]<1LL<<60) {
		FOR(y,N) if((m1&(1<<y))==0) { //初回
			int nm1,nm2;
			if(m2&(1<<x)) {
				nm1=m1|(1<<y);
				nm2=m2;
				dp[nm1][nm2][y]=min(dp[nm1][nm2][y],dp[m1][m2][x]+C[x][y]);
				if(nm1==(1<<N)-1) ret=min(ret,dp[nm1][nm2][y]);
			}
			else {
				nm1=(m1|(1<<y))^(1<<x);
				nm2=m2^(1<<x);
				dp[nm1][nm2][y]=min(dp[nm1][nm2][y],dp[m1][m2][x]+C[x][y]);
			}
		}
		
	}
	cout<<ret<<endl;
}

まとめ

1つ前のカードを戻す、ってところを正しく理解するのにかなり手間取った。