來源：牛客網：

烏龜棋

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 131072K，其他語言262144K 64bit IO Format: %lld

文章目錄

• • 烏龜棋
  • 題目描述
  • 題解：
  • 代碼：

題目描述

小明過生日的時候，爸爸送給他一副烏龜棋當作禮物。 烏龜棋的棋盤是一行N 個格子，每個格子上一個分數（非負整數）。棋盤第1 格是唯一的起點，第N 格是終點，游戲要求玩家控制一個烏龜棋子從起點出發走到終點。 

烏龜棋中M 張爬行卡片，分成4 種不同的類型（M 張卡片中不一定包含所有4 種類型的卡片見樣例），每種類型的卡片上分別標有1、2、3、4 四個數字之一，表示使用這種卡片后，烏龜棋子將向前爬行相應的格子數。游戲中，玩家每次需要從所有的爬行卡片中選擇一張之前沒有使用過的爬行卡片，控制烏龜棋子前進相應的格子數，每張卡片只能使用一次。游戲中，烏龜棋子自動獲得起點格子的分數，并且在后續的爬行中每到達一個格子，就得到該格子相應的分數。玩家最終游戲得分就是烏龜棋子從起點到終點過程中到過的所有格子的分數總和。
很明顯，用不同的爬行卡片使用順序會使得最終游戲的得分不同，小明想要找到一種卡片使用順序使得最終游戲得分最多。
現在，告訴你棋盤上每個格子的分數和所有的爬行卡片，你能告訴小明，他最多能得到多少分嗎？

輸入描述:
第1行2個正整數N和M，分別表示棋盤格子數和爬行卡片數。

第2行N個非負整數，a1, a2, ……, aN，其中ai表示棋盤第i個格子上的分數。

第3行M個整數，b1,b2, ……, bM，表示M張爬行卡片上的數字。
輸入數據保證到達終點時剛好用光M張爬行卡片，即N-1=

輸出描述:
輸出只有1行，1個整數，表示小明最多能得到的分數。
示例1
輸入
復制

9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1

輸出
復制

73

說明
小明使用爬行卡片順序為1，1，3，1，2，得到的分數為6+10+14+8+18+17=73。注意，

由于起點是1，所以自動獲得第1格的分數6。
示例2
輸入
復制

13 8 4 96 10 64 55 13 94 53 5 24 89 8 30 1 1 1 1 1 2 4 1

輸出
復制

455

備注:

題解：

動態規劃
dp[i][j][k][l]表示卡片1用了i張，卡片2用了j張，一次類推，用了這些卡牌的情況下所取得的最高分
那當前所在格子就是i1+j2+k3+l4
得到轉移方程：
dp[i][j][k][l]=max(dp[i?1][j][k][l],dp[i][j?1][k][l],dp[i][j][k?1][l],dp[i][j][k][l?1])+a[i×1+j×2+k×3+l×4]
第i×1+j×2+k×3+l×4格子的分數

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; const int maxn=50; int dp[maxn][maxn][maxn][maxn]; int num[10]; int a[1000]; int main() {int n,m;cin>>n>>m;for(int i=0;i<n;i++)cin>>a[i];for(int i=1;i<=m;i++){int w;cin>>w;num[w]++;//記錄每種卡牌的數量 }dp[0][0][0][0]=a[0];//切勿忘記起始格 for(int i=0;i<=num[1];i++){for(int j=0;j<=num[2];j++){for(int k=0;k<=num[3];k++){for(int l=0;l<=num[4];l++){int score=a[i*1+j*2+k*3+l*4];if(i-1>=0)dp[i][j][k][l]=max(dp[i-1][j][k][l]+score,dp[i][j][k][l]);if(j>=1)dp[i][j][k][l]=max(dp[i][j-1][k][l]+score,dp[i][j][k][l]);if(k>=1)dp[i][j][k][l]=max(dp[i][j][k-1][l]+score,dp[i][j][k][l]);if(l>=1)dp[i][j][k][l]=max(dp[i][j][k][l-1]+score,dp[i][j][k][l]);}}}}printf("%d\n",dp[num[1]][num[2]][num[3]][num[4]]);return 0; }

總結

以上是生活随笔為你收集整理的牛客网 【每日一题】7月27日题目精讲—乌龟棋的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。