题目描述 Description
这个游戏在一个有10*10个格子的棋盘上进行，初始时棋子位于左上角，终点为右下角，棋盘上每个格子内有一个0到9的数字，每次棋子可以往右方或下方的相邻格子移动，求一条经过数字之和最小且经过0到9的所有数字的合法路径，输出其长度。（经过的数字包括左上角和右下角）
输入描述 Input Description
输入包含10行，每行10个数字，以空格隔开，表示棋盘格子上的权值。数据保证存在合法路径。
输出描述 Output Description
输出所求路径的权值和。
样例输入 Sample Input
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 0
2 1 1 1 1 1 1 1 1 0
3 1 1 1 1 1 1 1 1 0
4 1 1 1 1 1 1 1 1 0
5 1 1 1 1 1 1 1 1 0
6 1 1 1 1 1 1 1 1 0
7 1 1 1 1 1 1 1 1 0
8 1 1 1 1 1 1 1 1 0
9 1 1 1 1 1 1 1 1 5
样例输出 Sample Output
50
样例解释
先一直向右走到第一行末尾，再竖直向下走位最优路径。
正解：状压DP
解题报告：
最近没事做，刷点状压DP水题。
f[i][j][s]记录到达(i,j)时状态为s的最优答案，显然可以吧0到9是否走过压成二进制。复杂度正确。
转移的时候注意一下状态这一维度要在最内层，开始样例都没过，才发现状态必须在最里层。。。
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#ifdef WIN32
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = ;
const int MAXS = (<<);
int n;
int a[MAXN][MAXN];
int f[MAXN][MAXN][MAXS]; inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline void solve(){
n=; memset(f,/,sizeof(f));
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
a[i][j]=getint();
int end=(<<n)-;
f[][][<<a[][]]=a[][];
//不能置为0！！！！！！只能从1出发 //for(int i=1;i<=n;i++)
// for(int j=1;j<=n;j++)
// f[i][j][0]=0; for(int j=;j<=n;j++)
for(int k=;k<=n;k++) {
if(j== && k==) continue;
for(int i=;i<=end;i++) {
if((<<a[j][k] | i )!=i) continue;
int lin=(<<);
lin=min(f[j-][k][i],f[j][k-][i]);
lin=min(lin,min(f[j-][k][i-(<<a[j][k])],f[j][k-][i-(<<a[j][k])]));
f[j][k][i]=lin+a[j][k];
}
}
printf("%d",f[n][n][end]);
} int main()
{
solve();
return ;
}