[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];
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology