杭电第一场补题

103.Mr. Liang play Card Game

题目： 有n张卡片，每一个卡片有自己的类型，等级、初始等级都是1。 有以下两种操作：

• 选择一张卡片打出去，获得权值为：val_{type_i}*p^{level-1}

• 选择两个相邻，且相同种类，相同等级的卡片进行合并，合并之后等级+1.

输出可以获得的最大权值。 思路：

数据范围： n<=100、level<=6、type<=20 因为只有相邻的两个位置才可以进行合并操作，所以考虑区间DP. n只有100，所以可以作为dp数组的两个下标。 因为合并的时候要求使得相邻的两个卡片的等级、种类是一样的，所以leve、type也作为两个dp数组下标。 考虑f[i][j][lv][tp] 表示在区间 [L,R] 中最后只剩下一张种类为tp.等级为lv的卡牌时候可以获得的最大权值。 用f[i][j][0][0]表示这个区间里面的所有卡牌都打出去的状态。

状态转移： 分为几种情况讨论

• 当L==R：

  • 如果如果此时需要的是f[l][r]][0][0]，就直接把当前的卡牌打出去即可： f[l][r][lv][tp]=val_{type_i}

  • 除了上述情况外，还有另外一种是可行的：位置为L的卡牌的种类刚好为当前需要的type且level为1的时候： f[l][t][lv][tp]=0

  • 其余情况都不可能存在，赋值为最小值即可。

• 当L<R:

  • 此时如果需要的是当前区间的卡牌都打完的状态：f[l][r][0][0] 第一种：枚举断点i，分为两个区间，把左右两个区间都打完的结果加起来即可： res=max(res,solve(l,i,0,0)+solve(i+1,r,0,0)) 第二种：枚举这个区间里面最后所剩下的一张牌的lv,type。并且加上对应的权值。

    res=max(res,solve(l,r,level,type)+val_{type_i}*p^{level-1}) 上述情况需要首先判断是否能够有这种情况，也就是solve函数结果是否>=0

  • 此时如果需要在区间里面最后剩下的牌的level为1： 枚举整个区间里面有没有对应的type，如果有就把除了这一张牌之外的所有卡牌都打出去即可： res=max(res,solve(l,i-1,0,0)+solve(i+1,r,0,0))

  • 如果level不为1： 直接枚举断点让左右区间分别提供一张卡牌，提供的卡牌的等级是当前需要的等级-1，种类和当前一样： res=max(res,solve(l,i,lv-1,type)+solve(i+1,r,lv-1,type))

  • 因为如果需要的剩下的卡牌的level为1，那么这张牌是不需要打出去的，如果level不为1，是一定需要凑出来了，两种情况中间有很大的差别，所以需要分两种情况来讨论。

• 当L>R:

  • 第一种：f[L][R][0][0]需要的是把卡牌打完，那么因为没有卡牌，输出0就可以。

  • 第二种：需要的不是卡牌打完，而是剩下某一种卡牌，此时应该返回的是最小值.

  • 上述两种情况，一种是可以存在但是提供的值是0，另外一种是不能存在，两者是有本质的区别的。

代码：

int dfs(int L,int R,int lv,int type){
    if(L>R) {
        if(lv==0) return 0;
        else return -INF;
    }
    if(L==R){
        if(lv==0 && type==0) return val[tp[L]];
        else if(lv==1 && type==tp[L]) return 0;
        return -INF;
    }
    if(f[L][R][lv][type]!=-1) return f[L][R][lv][type];
    int res=-INF;
    if(lv==0 && type==0){
        for(int i=L;i<R;i++){
            res=max(res,dfs(L,i,0,0)+dfs(i+1,R,0,0));
        }
        for(int i=1;i<=mxlv;i++){
            for(int j=1;j<=m;j++){
                if(dfs(L,R,i,j)>=0) res=max(res,dfs(L,R,i,j)+val[j]*base[i]);
            }
        }
    }
    else if(lv==1){
        for(int i=L;i<=R;i++){
            if(tp[i]==type){
                res=max(res,dfs(L,i-1,0,0)+dfs(i+1,R,0,0));
            }
        }
    }
    else{
        for(int i=L;i<=R;i++){
            res=max(res,dfs(L,i,lv-1,type)+dfs(i+1,R,lv-1,type));
        }
    }
    return f[L][R][lv][type]=res;
}
void solve(){
    cin>>n>>m>>mxlv>>p;
    memset(f,-1,sizeof(f));
    base[1]=1;
    for(int i=2;i<=mxlv;i++) base[i]=base[i-1]*p;
    for(int i=1;i<=n;i++) cin>>tp[i];
    for(int i=1;i<=m;i++) cin>>val[i];
    cout<<dfs(1,n,0,0)<<endl;
}