【OpenJudge 4124】海贼王之伟大航路（DP DFS）

航路（DP DFS）"/>

【OpenJudge 4124】海贼王之伟大航路（DP DFS）

海贼王之伟大航路

  OpenJ_Bailian - 4124 
两种解法： 第一种用DFS，用一个record数组保存每个状态最优解，大于这个值就剪枝不搜了。

#include<bits/stdc++.h>
#define INF 0X3f3f3f3f
#define LL long long
using namespace std;int n,a[20][20],ans,book[20],step,record[20][1<<15],weight[20],pos;
//record[i][j]表示通过j状态到达i岛时的最优路径，经过一个岛就加上那个岛的weight值。pos表示当前状态。
void dfs(int cur,int now) //cur是已经去过的岛的数目，now是现在在哪个岛
{if(cur+2 == n){step += a[now][n];if(step < ans)  ans=step;step -= a[now][n];return;}if(step>ans)return;for(int i = 2; i < n; ++i){if(!book[i]){if(record[i][pos+weight[i]] <= step+a[now][i])continue;step += a[now][i];pos += weight[i];book[i] = 1;record[i][pos] = step;dfs(cur+1,i);step -= a[now][i];pos -= weight[i];book[i] = 0;}}return;
}int main()
{for(int i = 1; i <= 16; ++i)weight[i] = 1 << i;while(~scanf("%d",&n)){pos = step = 0; ans = INF;memset(book,0,sizeof book);memset(record,INF,sizeof record);for(int i = 1; i <= n; ++i)for(int j = 1; j <= n; ++j)scanf("%d",&a[i][j]);dfs(0,1);printf("%d\n",ans);}return 0;
}