题解 – P1541 [NOIP2010 提高组] 乌龟棋

题目链接 – [NOIP2010 提高组] 乌龟棋

题目大意

你有一个数字串为地图，从pos = 1开始走，有4种走法，分别走1、2、3、4步，每种走法都有次数限制（最大不超过40），保证走完地图，求走完地图的最大分数。

分析

1.dp

很容易想到dp，数据范围不大，直接开多维：
dp[x1][x2][x3][x4]
在这个数组中，x1, x2, x3, x4 分别表示了已经取了各种走法几次，就有：
pos=x1+x2_2+x3_3+x4*4+1

2.状态转移

四层循环，我们要证明这样循环的顺序不会对答案造成影响。

for(int x1 = 0; x1 <= cards[1]; x1++)
for(int x2 = 0; x2 <= cards[2]; x2++)
for(int x3 = 0; x3 <= cards[3]; x3++)
for(int x4 = 0; x4 <= cards[4]; x4++)

首先，每次转移时都可以保证前面一个状态此时被更新过。
我们要想一下这个状态是否是最优的——每种状态的x_{1-4}实际上都对应着多种解，但是状态更新只更新一层，已经可以保证前面一层被更新过之后才来更新后一层，可以证明这样是无后效性的。

转移方程就比较简单了，见代码，稍微有一点点细节要注意。

3.滚动数组

仍然枚举四层，得到一个pos，这时候可以把dp数组第一维压掉，毕竟转移只用得到前面一层，每次把这一层的a[pos]加上即可。

AC代码

#include
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int MAXN = 500;
int n, m;
int a[MAXN], cards[5];
int dp[50][50][50][50];
int main()
{
  // freopen("P1541.in", "r", stdin);
  // freopen("P1541.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  int temp;
  for(int i = 1; i <= m; i++) {
    scanf("%d", &temp);
    cards[temp]++;
  }
  int pos = 1;
  dp[0][0][0][0] = a[1];
  for(int x1 = 0; x1 <= cards[1]; x1++) {
    for(int x2 = 0; x2 <= cards[2]; x2++) {
      for(int x3 = 0; x3 <= cards[3]; x3++) {
        for(int x4 = 0; x4 <= cards[4]; x4++) {
          int pos = x1 + x2 * 2 + x3 * 3 + x4 * 4 + 1;
          if(pos == 0) continue;
          if(x1 > 0) dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], dp[x1 - 1][x2][x3][x4] + a[pos]);
          if(x2 > 0) dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], dp[x1][x2 - 1][x3][x4] + a[pos]);
          if(x3 > 0) dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], dp[x1][x2][x3 - 1][x4] + a[pos]);
          if(x4 > 0) dp[x1][x2][x3][x4] = max(dp[x1][x2][x3][x4], dp[x1][x2][x3][x4 - 1] + a[pos]);
        }
      }
    }
  }
  printf("%d\n", dp[cards[1]][cards[2]][cards[3]][cards[4]]);
  return 0;
}