題目描述

解題思路

首先這是一個很明顯的線性dp的題目，很容易發現規律

數據輸入

我們用 h[ N ] 數組存儲每一個格子的分數

用 cnt [ ]，數組表示每一中卡片的數目

1，狀態表示

因為這里一個有4種跳躍方式可以選擇

f[ i ][ a ][ b ][ c ][ d ]表示 走到第 i 個格子的時候，1，2，3，4四種跳躍卡片分別用了，a，b，c，d張。

但是其實我們是可以去掉一維的，因為我們可以根據 1，2，3，4卡片的使用情況來推算我們當前到的位置 i = a + 2 * b + 3 * c + 4 * d

所以我們的狀態表示為

f[ a ][ b ][ c ][ d ]表示 走到第 i = a + 2 * b + 3 * c + 4 * d?個格子的時候，1，2，3，4四種跳躍卡片分別用了，a，b，c，d張。

2，狀態轉移方程

f[ a ][ b ][ c ][ d ]

=??max(f[ a - 1 ][ b ][ c ][ d ], f[ a ][ b - 1 ][ c ][ d ]，f[ a ][ b ][ c - 1 ][ d ] ，f[ a ][ b ][ c ][ d - 1] ) + h[ j ]

3，初始化

根據題目信息? “游戲中，烏龜棋子自動獲得起點格子的分數”

f[0][0][0][0] = h[0]，因為價值大于等于 0 ，其他的格子都初始化為 0 即可。

4，填表順序

咱們 4層for? 從 a 到 d，從小到大即可

5，最終答案?

f[ cnt[?1 ] ] [ cnt[ 2 ] ] [ cnt[ 3 ] ] [ cnt[ 4 ] ]

6，AC代碼

#include <iostream>
using namespace std;const int M = 45;
const int N = 360;int h[N] = { 0 };
int f[M][M][M][M] = { 0 };
int cnt[5] = { 0 };int n, m, sum;int main()
{cin >> n >> m;for (int i = 0; i < n; i++){cin >> h[i];}for (int i = 1; i <= m; i++){int x;cin >> x;cnt[x]++;}f[0][0][0][0] = h[0];for (int a = 0; a <= cnt[1]; a++){for (int b = 0; b <= cnt[2]; b++){for (int c = 0; c <= cnt[3]; c++){for (int d = 0; d <= cnt[4]; d++){int j = a + b * 2 + c * 3 + d * 4;if (a - 1 >= 0){f[a][b][c][d] = max(f[a][b][c][d], f[a - 1][b][c][d] + h[j]);}if (b - 1 >= 0){f[a][b][c][d] = max(f[a][b][c][d], f[a][b - 1][c][d] + h[j]);}if (c - 1 >= 0){f[a][b][c][d] = max(f[a][b][c][d], f[a][b][c - 1][d] + h[j]);}if (d - 1 >= 0){f[a][b][c][d] = max(f[a][b][c][d], f[a][b][c][d - 1] + h[j]);}}}}}cout << f[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;return 0;
}