Codeforces #321 Div2 D. Kefa and Dishes

うーん、難易度はともかく余りヒネリのない問題？
http://codeforces.com/contest/580/problem/D

問題

N個の料理があり、それぞれの満足度はA[i]である。

その際、K個の食べ合わせが与えられる。
各食べ合わせは、x番の料理の次にy番の料理を食べると満足度がc追加されるという形で表現される。

料理を最大M個任意の順番で食べるとき、合計満足度の最大値はいくつになるか。

解法

P(N,M)通り総当たりは当然できない。

ここはBitDPでdp[ここまで食べた料理のbitmask][最後に食べた料理番号] := ここまでの満足度最大値 を順に処理していけば良い。
O(N^2*2^N)の典型的なDPかな。

int N,M,K;
ll A[20];
ll mat[20][20];
ll dp[1<<18][18];

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

解法

ずいぶんオーソドックスな問題が出てきたなぁ…。