Educational DP Contest : U - Grouping

まぁここら辺は迷わなかったな。
https://atcoder.jp/contests/dp/tasks/dp_u

問題

N匹のウサギをいくつかのグループに分ける。
i番とj番のウサギが同じグループにいると得点A(i,j)が加算される、というテーブルAが与えられる。
得点の総和の最大値を求めよ。

解法

O(3^N)で解く典型問題。

f(mask) := maskの示す範囲のウサギがいくつかのグループを組んだ時の最高得点
とすると、f(0)=0から初めてf((2^N)-1)を求めたい。
f(mask)がわかっているとき、~maskの部分集合を総当たりしよう。

以下では、~maskの部分集合を総当たりする際、先頭だけは絶対グループに入る、と決め打ちして若干高速化しているが、おそらく不要。

int N;
int A[16][16];
ll SA[1<<16];
ll dp[1<<16];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(y,N) FOR(x,N) cin>>A[y][x];
	int mask;
	FOR(mask,1<<N) {
		FOR(x,N) FOR(y,x) if((mask&(1<<x))&&(mask&(1<<y))) SA[mask]+=A[x][y];
		dp[mask]=-1LL<<60;
	}
	dp[0]=0;
	FOR(mask,(1<<N)-1) {
		int first;
		FOR(first,N) if((mask&(1<<first))==0) break;
		int submask=((1<<N)-1)^mask^(1<<first);
		for(int sm2=submask; sm2>=0; sm2--) {
			sm2&=submask;
			
			dp[mask | sm2 | (1<<first)] = max(dp[mask | sm2 | (1<<first)], dp[mask] + SA[sm2 | (1<<first)]);
		}
	}
	
	cout<<dp[(1<<N)-1]<<endl;
}

まとめ

ここら辺も昔は苦手だったけど成長したもんだ。