[TIOJ] 1390. 鍊金術

題目連結:http://tioj.infor.org/problems/1390

---

看到n這麼小就合理猜個狀態壓縮DP，稍微想個兩下應該可以發現轉移式$dp[S] = \max\limits_{i,j \in S}(dp[S-not \_ left[i][j]] + val[i][j])$，也就是說對於一個集合，找到使得他最大的一組i,j。

#include <bits/stdc++.h>
using namespace std;

const int N = 15+1;

int n, val[N][N], lef[N][N];
int dp[1<<N];
bitset<(1<<N)> dped;

inline bool inS(int,int);
int f(int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	while(cin>>n){
		dped.reset();
		fill(dp, dp+(1<<(n+1)), 0);
		dped[0]=1;
		for(int i=0;i<n;i++) dped[1<<i]=1;
		for(int i=0;i<n;i++) for(int j=0;j<n;j++)
			cin>>val[i][j];
		for(int i=0;i<n;i++) for(int j=0;j<n;j++)
			cin>>lef[i][j];
		cout<<f((1<<n) - 1)<<'\n';
	}
	return 0;
}

inline bool inS(int x, int S){
	return (S)&(1<<x);
}

int f(int S){
	if(dped[S]) return dp[S];
	dped[S]=1;
	for(int i=0;i<n;i++){
		if(!inS(i, S)) continue;
		for(int j=i+1;j<n;j++){
			if(!inS(j, S))continue;
			dp[S]=max(dp[S], f(S-(1<<i)-(1<<j)+(1<<lef[i][j]))+val[i][j]);
		}
	}
	return dp[S];
}