洛谷1541 乌龟棋

Luogu

分析

这是一道较水的DP题。
我们用$f[i][j][k][l]$表示用i张1、j张2、k张3、l张4所能达到的最大分数。
自然写出状态转移方程:
$f[i][j][k][l]=max(f[i-1][j][k][l],f[i][j-1][k][l],f[i][j][k-1][l],f[i][j][k][l-1])+a[1+i+2j+3k+4l]$

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
int s[5],a[351];
int f[41][41][41][41];
int main()
{
    int n,m,in;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&in);
        s[in]++; //输入时统计第i种牌的数量  
    }
    for (int i=0;i<=s[1];i++) //核心DP代码  
        for (int j=0;j<=s[2];j++)
            for (int k=0;k<=s[3];k++)
                for (int l=0;l<=s[4];l++)
                    f[i][j][k][l]=max(max(max(f[max(0,i-1)][j][k][l],f[i][max(0,j-1)][k][l]),f[i][j][max(0,k-1)][l]),f[i][j][k][max(0,l-1)])+a[1+i+2*j+3*k+4*l];
    printf("%d\n",f[s[1]][s[2]][s[3]][s[4]]); //输出  
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 04 PM

发表评论