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

· · 题解

题目大意

给 n 个格子，每个格子上都有一定的分数。再给 m 张数值为 1 到 4 的卡片，卡片上的数值代表前进的步数，每张卡片只能用一次。每到达一个格子就可以拿走该分数，问所有卡片用光时能够获得的最大分数。

解题思路

一眼动态规划，上动态规划六步分析法。

一、定义问题状态

题目中共计四种卡片，每种卡片的数量与得分之间有联系，状态非常好设计。

### 二、分解子问题 分解子问题的目的是将问题拆分为相似的规模更小的问题，从而得到，子问题与原问题之间的**状态转移方程**。分解子问题时需要考虑，决策与约束条件。 $$f(a,b,c,d)=\max\begin{cases}f(a-1,b,c,d) + sc[step] & a\ge 1\\ f(a,b-1,c,d) + sc[step] & b\ge 1\\ f(a,b,c-1,d) + sc[step] & c\ge 1\\f(a,b,c,d-1) + sc[step] & d\ge 1\end{cases}$$ 其中 $ step=a+2\times b+3\times c+4\times d+1

三、初始化边界状态

边界状态即为不需要计算就能直接分析出的状态。这里是一张卡片都没有用时得分为在第 1 格处的分数。

f(0,0,0,0)=sc[1]

四、计算顺序

从小到大依次枚举卡片 1 至 4 的张数。

五、最终答案

ans=f(cnt1,cnt2,cnt3,cnt4)

其中 cnt1 至 cnt4 表示第 1 至第 4 张卡片的总数量。

六、效率分析

时间复杂度和空间复杂度度都为 O(n^4) 这里 n 代表每种卡片的最大数量为 40 没有超时和超空间。

代码实现

#include<bits/stdc++.h>
using namespace std;

const int maxn = 10005;
int n, m, a[maxn], b, cnt[5], f[52][52][52][52];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= m; i++){
        cin >> b;
        cnt[b]++;
    }
    f[0][0][0][0] = a[1];
    for(int i = 0; i <= cnt[1]; i++)
        for(int j = 0; j <= cnt[2]; j++)
            for(int k = 0; k <= cnt[3]; k++)
                for(int l = 0; l <= cnt[4]; l++){
                    int step = i+2*j+3*k+4*l+1;
                    if(i) f[i][j][k][l] = max(f[i][j][k][l], f[i-1][j][k][l] + a[step]);
                    if(j) f[i][j][k][l] = max(f[i][j][k][l], f[i][j-1][k][l] + a[step]);
                    if(k) f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k-1][l] + a[step]);
                    if(l) f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l-1] + a[step]);
                }
    cout << f[cnt[1]][cnt[2]][cnt[3]][cnt[4]];
    return 0;
}