原題傳送門(mén)

一道比較簡(jiǎn)單易懂的線(xiàn)性DP題：

設(shè)狀態(tài)dp[a][b][c][d]表示使用數(shù)量分別為a, b, c, d張的不同的牌

num數(shù)組存儲(chǔ)每一個(gè)位置的分值

r = a + b * 2 + c * 3 + d * 4 + 1，表示當(dāng)前的位置

則有 if(a)
( dp [ a ] [ b ] [ c ] [ d ] = max ( dp [ a - 1] [ b ] [ c ] [ d ] + num [ r ] , dp [ a ] [ b ] [ c ] [ d] )

因?yàn)榭梢灾苯荧@得初始位置的分?jǐn)?shù)，所以邊界條件為 dp [ 0 ] [ 0 ] [ 0 ] [ 0 ] = num [ 1 ]

得到狀態(tài)轉(zhuǎn)移方程后，本題就解決了

#include <bits/stdc++.h> int n, m, tot; int num[410], g[5]; int dp[40][40][40][40]; inline int read() {int x = 0, f = 1;char ch = getchar();while (!isdigit(ch))f = (ch == '-') ? -1 : 1, ch = getchar();while (isdigit(ch))x = x * 10 + ch - '0', ch = getchar();return x * f; } int main() {n = read(), m = read();for (int i = 1; i <= n; i++)num[i] = read();for (int i = 1; i <= m; i++)tot = read(), g[tot]++;dp[0][0][0][0] = num[1];for (int a = 0; a <= g[1]; a++)for (int b = 0; b <= g[2]; b++)for (int c = 0; c <= g[3]; c++)for (int d = 0; d <= g[4]; d++){int r = a + b * 2 + c * 3 + d * 4 + 1;if (a)dp[a][b][c][d] = std::max(dp[a - 1][b][c][d] + num[r], dp[a][b][c][d]);if (b)dp[a][b][c][d] = std::max(dp[a][b - 1][c][d] + num[r], dp[a][b][c][d]);if (c)dp[a][b][c][d] = std::max(dp[a][b][c - 1][d] + num[r], dp[a][b][c][d]);if (d)dp[a][b][c][d] = std::max(dp[a][b][c][d - 1] + num[r], dp[a][b][c][d]);}std::cout << dp[g[1]][g[2]][g[3]][g[4]] << std::endl;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/wyctstf/p/11281057.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P1541 乌龟棋的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。