洛谷—P1541 乌龟棋题解

题目链接： P1541 乌龟棋
解题思路： 因为当前的状态与我们用过的牌有关，所以用一个四维数组记录当前已经用掉的牌数dp[a][b][c][d],这个状态可以由上一个状态dp[a - 1][b][c][d]、dp[a][b - 1][c][d]、dp[a][b][c - 1][d]、dp[a][b][c][d - 1]转移而来。所以我们可以枚举每种牌的数量，计算使用当前状态的牌到达的位置即可。

	for (int a = 0; a <= f[1]; a++) {
    for (int b = 0; b <= f[2]; b++) {
    for (int c = 0; c <= f[3]; c++) {
    for (int d = 0; d <= f[4]; d++) {
    int s =1 + 1 * a + 2 * b + 3 * c + 4 * d;//计算使用当前状态的牌到达的位置if(a>0) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a - 1][b][c][d] + num[s]);if(b>0) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b - 1][c][d] + num[s]);if(c>0) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b][c - 1][d] + num[s]);if(d>0) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b][c][d - 1] + num[s]);}}}}

代码：

#include<iostream>
using namespace std;
const int maxn = 1000;
int n, m;
int dp[50][50][50][50],num[maxn],f[maxn],temp;
int main() {
    cin >> n >> m;for (int i = 1; i <= n; i++) {
    cin >> num[i];}for (int i = 1; i <= m; i++) {
    cin >> temp;f[temp]++;}dp[0][0][0][0] = num[1];for (int a = 0; a <= f[1]; a++) {
    for (int b = 0; b <= f[2]; b++) {
    for (int c = 0; c <= f[3]; c++) {
    for (int d = 0; d <= f[4]; d++) {
    int s =1 + 1 * a + 2 * b + 3 * c + 4 * d;if(a>0) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a - 1][b][c][d] + num[s]);if(b>0) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b - 1][c][d] + num[s]);if(c>0) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b][c - 1][d] + num[s]);if(d>0) dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b][c][d - 1] + num[s]);}}}}cout << dp[f[1]][f[2]][f[3]][f[4]] << endl;return 0;
}