乌龟棋

题目描述

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行N 个格子，每个格子上一个分数（非负整数）。棋盘第1 格是唯一的起点，第N 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中M 张爬行卡片，分成4 种不同的类型（M 张卡片中不一定包含所有4 种类型的卡片见样例），每种类型的卡片上分别标有1、2、3、4 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入描述:

第1行2个正整数N和M，分别表示棋盘格子数和爬行卡片数。
第2行N个非负整数，a1, a2, ……, aN，其中ai表示棋盘第i个格子上的分数。
第3行M个整数，b1,b2, ……, bM，表示M张爬行卡片上的数字。
输入数据保证到达终点时刚好用光M张爬行卡片，即

输出描述:

输出只有1行，1个整数，表示小明最多能得到的分数。

题解

一开始最直观的想法是设置一个dp[n][a1][a2][a3][a4][a5]表示在第n个格子上时还剩下a1个走一步的卡片，a2个走两步的卡片，a3个走三步的卡片，a4个走四步的卡片时可以获得分数的最大值。
后来稍微一算，爆空间了...
所以接下来我就在思考怎么精简状态。
我略微细想了一下，a1，a2，a3，a4，a5是不能够省略的。那这个n是否有必要呢？题干中有关键的一句话输入数据保证到达终点时刚好用光M张爬行卡片，所以这个n我们是可以用剩下四个状态来推出来的，也就是说n是一个冗余的状态。
所以剩下我们就愉快的四维dp写记忆化就完美啦^.^
以后要按时写题了，这两天有点懈怠呜呜呜

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=360;
int n,m;
int a[N];
int b[5];
int dp[40][40][40][40];
int dfs(int x,int y,int k,int z){
    if(dp[x][y][k][z])
        return dp[x][y][k][z];
    int maxn=0,id=x+y*2+k*3+z*4+1;
    if(x)maxn=max(dfs(x-1,y,k,z)+a[id],maxn);
    if(y)maxn=max(dfs(x,y-1,k,z)+a[id],maxn);
    if(k)maxn=max(dfs(x,y,k-1,z)+a[id],maxn);
    if(z)maxn=max(dfs(x,y,k,z-1)+a[id],maxn);
    return dp[x][y][k][z]=maxn;
}
////////////////////////////////////////////////////////////////////////
int main(){
    n=gn(),m=gn();
    repi(i,1,n)a[i]=gn();
    repi(i,1,m)b[gn()]++;
    dp[0][0][0][0]=a[1];
    cout<<dfs(b[1],b[2],b[3],b[4])<<endl;
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/