题目内容

P1541

大意:乌龟棋的棋盘是一行 N 个格子,每个格子上一个分数(非负整数)。棋盘第 1 格是唯一的起点,第 N 格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

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

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

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

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

解题思路

想到卡片的使用顺序可能影响到最终获得的分数,就需要使用 dp,设 f(i,j,k,l) 表示 4 种卡片分别使用了 i,j,k,l 张,则这一个状态可以由四个之前的状态递推而来(只要不为 0,可以选 1~4 号卡中的任意一个)。

方程:

f(i,j,k,l)=\max\lbrace f(i,j,k,l),f(i-1,j,k,l),f(i,j-1,k,l),f(i,j,k-1,l),f(i,j,k,l-1)\rbrace+a_{i+2j+3k+4l+1}

代码:

#include <cstdio>

const int maxn=355,maxg=41;
int n,m,g[5],a[maxn],f[maxg][maxg][maxg][maxg];

inline int max(int a,int b)
{
    return a>b?a:b;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    register int x;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        g[x]++;
    }
    f[0][0][0][0]=a[1];
    for(int i=0;i<=g[1];i++)
        for(int j=0;j<=g[2];j++)
            for(int k=0;k<=g[3];k++)
                for(int l=0;l<=g[4];l++)
                {
                    int r=i+j*2+k*3+l*4+1;
                    if(i)
                        f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[r]);
                    if(j)
                        f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[r]);
                    if(k)
                        f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[r]);
                    if(l)
                        f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[r]);
                }
    printf("%d\n",f[g[1]][g[2]][g[3]][g[4]]);
    return 0;
}
最后修改日期: 2020年3月4日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。