loj 1011(状态压缩+记忆化搜索)

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=25837

思路：状态压缩+记忆化搜索。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define FILL(a,b) memset(a,b,sizeof(a))
 7 
 8 int dp[1<<17],map[17][17];
 9 int n;
10 
11 int dfs(int state,int m)
12 {
13     if(state==0)return 0;
14     if(dp[state])return dp[state];
15     for(int i=0;i<n;i++){
16         if(state&(1<<i)){
17             dp[state]=max(dp[state],dfs(state&~(1<<i),m-1)+map[i][m]);
18         }
19     }
20     return dp[state];
21 }
22 
23 int main()
24 {
25     int _case,t=1;
26     scanf("%d",&_case);
27     while(_case--){
28         scanf("%d",&n);
29         for(int i=0;i<n;i++)
30             for(int j=0;j<n;j++)scanf("%d",&map[i][j]);
31         FILL(dp,0);
32         printf("Case %d: %d
",t++,dfs((1<<n)-1,n-1));
33     }
34     return 0;
35 }

View Code