【动态规划】洛谷_1541 乌龟棋

本文主要是介绍【动态规划】洛谷_1541 乌龟棋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出$N$个格子，上面有一些分数，有$M$张卡片，每张卡片上标有$1,2,3,4$这些数字中其中一个，代表使用这张卡片能前进那么多格，每张卡片只能使用一次。
使用不同顺序的卡片可以获得不同的分数，求最大分数。

思路

动态规划。
设$F[a][b][c][d]$代表第一种牌用了$a$张，第二种牌用了$b$张，第三……的最大分数，可以得出动态转移方程：
$F[a+1][b][c][d]=max(f[a+1][b][c][d],f[a][b][c][d]+A[t])$
$F[a][b+1][c][d]=max(f[a][b+1][c][d],f[a][b][c][d]+A[t])$
……
其中$A[t]$代表使用那么多卡片之后到达的格子上的分数。

代码

#include<cstdio>
#include<algorithm>int N, M;
int A[351], B[121], F[41][41][41][41], sum[5];int main() {scanf("%d %d", &N, &M);for (int i = 1; i <= N; i++)scanf("%d", &A[i]);for (int i = 1; i <= M; i++) {scanf("%d", &B[i]);sum[B[i]]++;}F[0][0][0][0] = A[1];for (int a = 0; a <= sum[1]; a++) for (int b = 0; b <= sum[2]; b++)for (int c = 0; c <= sum[3]; c++)for (int d = 0; d <= sum[4]; d++) {int t = a * 1 + b * 2 + c * 3 + d * 4 + 1;F[a + 1][b][c][d] = std::max(F[a + 1][b][c][d], F[a][b][c][d] + A[t + 1]);F[a][b + 1][c][d] = std::max(F[a][b + 1][c][d], F[a][b][c][d] + A[t + 2]);F[a][b][c + 1][d] = std::max(F[a][b][c + 1][d], F[a][b][c][d] + A[t + 3]);F[a][b][c][d + 1] = std::max(F[a][b][c][d + 1], F[a][b][c][d] + A[t + 4]);}printf("%d", F[sum[1]][sum[2]][sum[3]][sum[4]]);
}

这篇关于【动态规划】洛谷_1541 乌龟棋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---