[动态规划] pku1185 状态压缩 at GCCFeli.cn

[动态规划] pku1185 状态压缩

评论45次阅读2007.09.30 22:09; 作者：Felicia　

经典的状态压缩DP，状态是f[i][j]，表示第i行，以3进制j为状态。j的位代表一个格子，只能是：0表示第i行和第i – 1行都没有炮兵，1表示第i行没有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS进行状态转移。一开始我做了超时，后来预处理了一下合法状态，快了不少，才AC。

下面是我的代码

下载: pku1185.cpp

/**********************************************************************
Author: WHU_GCC
Created Time: 2007-9-29 20:53:51
File Name: pku1185.cpp
Description:
**********************************************************************/
#include <iostream>
using namespace std;

#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

const int maxn = 110;
const int maxm = 11;
const int mask[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323};

int n, m;
int g[maxn][maxm];
int f[maxn][59049];
int ok_state[10000];
int len;
int bits[14];

inline int get_bit(int x, int k)
{
   return x % mask[k + 1] / mask[k];
}

void dfs(int origin_state, int origin_line, int now_col, int delta)
{
   if (now_col >= m)
   {
   int new_state = 0;
   for (int i = 0; i < m; i++)
   if (bits[i] > 0)
   new_state += bits[i] * mask[i];

   f[origin_line + 1][new_state] >?= f[origin_line][origin_state] + delta;
   return;
   }
   if (bits[now_col] == -1 && g[origin_line + 1][now_col] == 0)
   {
   bits[now_col] = 2;
   dfs(origin_state, origin_line, now_col + 3, delta + 1);
   bits[now_col] = -1;
   }
   dfs(origin_state, origin_line, now_col + 1, delta);
}

void dfs1(int now_col, int new_state, int last1, int last2)
{
   if (now_col >= m)
   {
   ok_state[len++] = new_state;
   return;
   }

   if (last1 != 2 && last2 != 2)
   dfs1(now_col + 1, new_state + 2 * mask[now_col], 2, last1);
   if (last1 != 1 && last2 != 1)
   dfs1(now_col + 1, new_state + mask[now_col], 1, last1);
   dfs1(now_col + 1, new_state, 0, last1);
}

void pre_process()
{
   len = 0;
   dfs1(0, 0, -1, -1);
}

int dp()
{
   memset(f, -1, sizeof(f));
   f[0][0] = 0;
   for (int i = 0; i < n; i++)
   {
   for (int j = 0; j < len; j++)
   if (f[i][ok_state[j]] != -1)
   {
   for (int k = 0; k < m; k++)
   bits[k] = get_bit(ok_state[j], k) - 1;
   dfs(ok_state[j], i, 0, 0);
   }
   }
   int ret = 0;
   for (int i = 0; i < mask[m]; i++)
   ret >?= f[n][i];
   return ret;
}

int main()
{
   char s[22];
   scanf("%d%d", &n, &m);
   for (int i = 1; i <= n; i++)
   {
   scanf("%s", s);
   for (int j = 0; j < m; j++)
   if (s[j] == 'P')
   g[i][j] = 0;
   else
   g[i][j] = 1;
   }
   pre_process();
   printf("%d\n", dp());
   return 0;
}

标签云: 代码, 动态规划 | 日志分类: 动态规划

如需转载烦请添加以下信息: 本文转自Felicia@GCCFeli.cn

评论 (0)
引用通告 (0)
发表评论引用通告

暂无评论.

暂无引用通告

发表回复