洛谷 P1541 [NOIP2010 提高组] 乌龟棋

思路：暴力DP‘“

其实在想到暴力dp之前，作者寻思着这个题目可能和”摆花“那道题差不多，就用那种思想想了一下，结果其实不是这样的。这里并不能开二维进行推进。由于我们在二维表示的时候，代表的含义就是在走了i个格子用了j个票子所积累到的最大积分。

其实DP思路上看起来是没有什么错误的，但是呢，我这里忽略掉了：这里的票子是分种类的，也就是说，这里的票子并不是自由选的，我们必须保证这个票子正好用完，并且每一种票子是用一次的，并不能重复使用。这里可以用01背包的思路，但是呢，我们还需要保证它走的路数正好和票数是对上的，也就是票数必须是正好才行，在这种情况下求最大价值。我们如果用01背包那种思想，其实就是在用完n张票子之前就已经选中了最佳的情况，但是不一定就是正好用完五张票子最大的价值，可能是我们在遍历过程中重复使用票子得到的结果，而我们在这样的情况下并不能进行约束。所以我们需要换一种思想。

后来，可以发现我们需要用这种暴力的方法来做。这样暴力的话很好懂了。

四维数组开起来之后，我们就直接专心应对所需要的卡片数进行比较就行了，加上我们走到这个当前格子的积分求出来最大值就行了。

注意：在求最大积分的时候，我们不要忘记在不用任何票子的时候我们的状态是第一个格子的积分，因为我们总是从这个起点开始走。好了，还有一点就是我们在转移的时候，加上格子积分的时候我们需要额外+1.也就是+1+a*1+b*2+c*3+d*4.为什么呢？因为我们在前面已经加上第一个格子的积分了，所以我们不能再从1开始加了，这样的话不仅很难发现错误，并且还会导致结果错。

上代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath> 
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_map>
#include<set>
#define int long long
#define MAX 4400
#define inf 0x3f3f3f3f
#define _for(i,a,b) for(int i=a;i<(b);i++)
using namespace std;
typedef pair<int, int> PII;
int n,m;
int counts;
int dx[] = { 0,1,0,-1};
int dy[] = { 1,0,-1,0 };
int arr[MAX];
int piao[MAX];
int dp[50][50][50][50];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dp[0][0][0][0] = arr[1];
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        piao[x]++;
    }
    for (int a = 0; a <= piao[1]; a++) {
        for (int b = 0; b <= piao[2]; b++) {
            for (int c = 0; c <= piao[3]; c++) {
                for (int d = 0; d <= piao[4]; d++) {
                    int r = 1 + a * 1 + b * 2 + c * 3 + d * 4;
                    if (a != 0) 
                        dp[a][b][c][d] = max(dp[a - 1][b][c][d]+arr[r], dp[a][b][c][d]);
                    if (b != 0)
                        dp[a][b][c][d] = max(dp[a][b - 1][c][d]+arr[r], dp[a][b][c][d]);
                    if (c != 0)
                        dp[a][b][c][d] = max(dp[a][b][c - 1][d]+arr[r], dp[a][b][c][d]);
                    if (d != 0)
                        dp[a][b][c][d] = max(dp[a][b][c][d], dp[a][b][c][d - 1]+arr[r]);
                        
                }
            }
        }
    }
    cout << dp[piao[1]][piao[2]][piao[3]][piao[4]];
    return 0;
}