启蒙

DP的思想自从进入ACM队之后就有所了解，虽然偶尔做出过几道题，但是还是停留在“有所理解”的层次上。昨天做了HDU_5067，在聪明的卓君的教导下，突然感觉新世界的大门打开了……

思考

dp的思想并不复杂，总结起来就是状态转移。但是难就难在如何找到转移方程，如何用数组或者其它方式来表示状态。由于dp的题目很灵活，没有固定的模式，所以要把握思想，勤于思考，说不定能多过两道题。

题意

在一张地图上，有10个以内的特殊格子，现在你从1,1点出发，经过所有特殊点并返回1,1点。图中可以走回头路。求最少步数。

思路

思考半个小时就打算暴力dfs，反正就10个点，也就10!次计算呗。但是这不是最优解法。从dp的角度来思考这道题，看看能不能更好？
首先有10个点，可以用10位长的bit来表示当前状态，1表示第i个点已经走过了，0表示没走过。最多1024就能表示所有状态。这是第一维。
其次如何表示当前所选择的点呢？用第二维来表示当前状态最后经过的是第几个点，一共是10个点嘛。
组合dp[1<<10][10]的状态就能表示所有情况。例如dp[1001001001]4表示当前已经走过1,4,7,10这四个点，且最后一个点是4的状态下的最短路。
细节再算距离时，特殊的点1,1要把它普通化，详见代码。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int m,n;int dp[(1<<11)][12],cnt=0;
struct stone{
	int x,y;
}ss[12];
inline int dis(stone a,stone b){
	return abs(a.x-b.x)+abs(a.y-b.y);
}
int dfs(int state,int pos){
	if(dp[state][pos]!=-1) return dp[state][pos];
	bool digtal[12];memset(digtal,0,sizeof(digtal));
	int tmp=state,cn=0;
	while(tmp){
		digtal[cn++]=tmp&1;
		tmp>>=1;
	}
	int ans=inf;
	for(int i=0;i<=cnt;i++){
		if(!digtal[i]){
			tmp=(1<<i)+state;
			int tt=dfs(tmp,i)+dis(ss[pos],ss[i]);
			ans=min(tt,ans);
		}
	}
	if(ans== inf) return dp[state][pos]=dis(ss[pos],ss[0]);
	return dp[state][pos]=ans;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF){
		memset(ss,0,sizeof(ss));cnt=0;
		memset(dp,-1,sizeof(dp));
		ss[0].x=0;ss[0].y=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++){
				int tmp;
				scanf("%d",&tmp);
				if(tmp){
					ss[++cnt].x=i;ss[cnt].y=j;
				}
			}
		printf("%d\n",dfs(1,0));
	}
	return 0;
}