yukicoder : No.357 品物の並び替え (Middle)

これは割と典型。
http://yukicoder.me/problems/810

問題

N個の品物を順に並べる。
品物iより品物jを先に並べるとscoreが得られる、というようなルールが複数与えられる。

最適な並べ方をしたとき、scoreの最大値を求めよ。

解法

典型的なbitDP問題。
既に並べ終わった品物をbitmaskで表し、次に置く品物を総当たりしていこう。

int N,M;
int mat[20][20];
int dp[1<<15];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y>>r;
		mat[x][y]=r;
	}
	for(int mask=0;mask<1<<N;mask++) {
		FOR(i,N) if((mask&(1<<i))==0) {
			x = 0;
			FOR(j,N) if(mask&(1<<j)) x += mat[j][i];
			dp[mask | (1<<i)] = max(dp[mask | (1<<i)],dp[mask]+x);
		}
	}
	cout<<dp[(1<<N)-1]<<endl;
}

まとめ

356,357は★2.5位で、355が★3っぽい感触でした。