codevs1358 棋盘游戏

题目描述 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

样例解释

先一直向右走到第一行末尾，再竖直向下走位最优路径。

正解：状压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 ;

 }

巴特西

codevs1358 棋盘游戏

最新文章

热门文章