洛谷 P1541 乌龟棋

佚名 6年前 (2019-05-11) 随笔 1621人围观抢沙发百度已收录

设计状态:f[i][j][k][l]表示第一种牌已经用了i张，第二种牌已经用了j张，第三种牌已经用了k张,第四种牌已经用了l张时的最大价值

转移：考虑再用一张牌，等于从少用这么一张牌的最大价值加上用了这一张牌后踩到的格子上的分。具体见代码

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[351],f[41][41][41][41],n1=0,n2=0,n3=0,n4=0;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        if(x==1){
            n1++;
        }
        if(x==2){
            n2++;
        }
        if(x==3){
            n3++;
        }
        if(x==4){
            n4++;
        }
    }
    f[0][0][0][0]=a[1];
    for(int i=0;i<=n1;i++){
        for(int j=0;j<=n2;j++){
            for(int k=0;k<=n3;k++){
                for(int l=0;l<=n4;l++){
                    int now=1+i+j*2+k*3+l*4;
                    if(i!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[now]);
                    if(j!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[now]);
                    if(k!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[now]);
                    if(l!=0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[now]);
                }
            }
        }
    }
    printf("%d",f[n1][n2][n3][n4]);
    return 0;
}