[NOIP2010 提高组] 乌龟棋

题目背景

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

题目描述

乌龟棋的棋盘是一行 NN 个格子，每个格子上一个分数（非负整数）。棋盘第 11 格是唯一的起点，第 NN 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 MM 张爬行卡片，分成 44 种不同的类型（MM 张卡片中不一定包含所有 44 种类型的卡片，见样例），每种类型的卡片上分别标有 1,2,3,41,2,3,4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。

游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式

每行中两个数之间用一个空格隔开。

第 11 行 22 个正整数 N,MN,M，分别表示棋盘格子数和爬行卡片数。

第 22 行 NN 个非负整数，a1,a2,…,aNa1​,a2​,…,aN​，其中 aiai​ 表示棋盘第 ii 个格子上的分数。

第 33 行 MM 个整数，b1,b2,…,bMb1​,b2​,…,bM​，表示 MM 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光MM张爬行卡片。

输出格式

11 个整数，表示小明最多能得到的分数。

输入输出样例

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

73

说明/提示

每个测试点 1s。

小明使用爬行卡片顺序为 1,1,3,1,21,1,3,1,2，得到的分数为 6+10+14+8+18+17=736+10+14+8+18+17=73。注意，由于起点是 11，所以自动获得第 11 格的分数 66。

对于 30%30% 的数据有 1≤N≤30,1≤M≤121≤N≤30,1≤M≤12。

对于 50%50% 的数据有 1≤N≤120,1≤M≤501≤N≤120,1≤M≤50，且 44 种爬行卡片，每种卡片的张数不会超过 2020。

对于 100%100% 的数据有 1≤N≤350,1≤M≤1201≤N≤350,1≤M≤120，且 44 种爬行卡片，每种卡片的张数不会超过 4040；0≤ai≤100,1≤i≤N,1≤bi≤4,1≤i≤M0≤ai​≤100,1≤i≤N,1≤bi​≤4,1≤i≤M。

一看到这个，就感觉和背包很像，于是就随手写了一个错的。。
大概是f[i][j]表示已经考虑到了第i个牌，然后当前走到了第j个格子。。
问题就是，这个解法是背包的，背包不考虑物品放入的顺序，这对他没有意义。。
这个要考虑，如果第i个牌暂时没有用，我们选择将它跳过，但是之后在想用的时候，我们是做不到的
所以顺序必要的时候，这种状态是完全处理不了的。

要考虑换一种做法
我们发现对于这个题目，有一个奇怪的条件，就是每一步的卡片数量是确定的
那我们其实可以直接把卡片数量记录下来啊
设f[i][j][k][h]表示用了i张走一步的卡片，j张走两步的牌，k张走3步的，走到了第h格的最大得分
看到这个状态，这题就出来了。。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
    char c=getchar();int a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int f[41][41][41][41],n,m,a[351],b[5];
int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=1;i<=m;i++)
    {
        b[read()]++;
    }
    f[0][0][0][0]=a[1];
    for(int i=0;i<=b[1];i++)
    {
        for(int j=0;j<=b[2];j++)
        {
            for(int k=0;k<=b[3];k++)
            {
                for(int h=0;h<=b[4];h++)
                {
                    int step=1+i+j*2+k*3+h*4;
                    if(i!=0)
                        f[i][j][k][h]=max(f[i][j][k][h],f[i-1][j][k][h]+a[step]);
                    if(j!=0)
                        f[i][j][k][h]=max(f[i][j][k][h],f[i][j-1][k][h]+a[step]);
                    if(k!=0)
                        f[i][j][k][h]=max(f[i][j][k][h],f[i][j][k-1][h]+a[step]);
                    if(h!=0)
                        f[i][j][k][h]=max(f[i][j][k][h],f[i][j][k][h-1]+a[step]);
                        
                }
            }
        }
    }
    cout<<f[b[1]][b[2]][b[3]][b[4]]<<endl;
    return 0;
}

这题主要是可以学习到一种关于顺序的dp
虽然这题中有每种牌类型的限制的条件，但是这种思路是值得学习的，特别是关于状态的设计
可以说是把原本需要枚举全排列的问题完美的解决了

因为我们其实是不关注前面的牌是怎么排列的，前面怎么排列其实对于后面的决策可以说是完全没有一点点影响
唯一的可以说是影响后面的只有答案，这还是对后面的决策没有影响（有影响还怎么dp。。

和顺序有关的题目，经典的就是路径问题
就像是之前那个传纸条，我们一直向着右下走，其实也是一样决定了前面的路径和后面的决策没有联系,而对后面决策有影响的“位置”被我们给放进了状态之中

也许我可以得出一个不坚固的结论，就是和顺序有关的题目，除了状压，我们能够做的就是尽量不去关注前面的路径，而是专注于我们目前所在的位置，或者说是状态能够记录的
否则没法做。。。

嗯