题解：P10236 [yLCPC2024] D. 排卡

· · 题解

题目传送门

怎么感觉 T4 比 T3 简单啊（因为我不会 T3）。

题意简述

有一个长度为 n 的序列 a，你每次能从左端点或右端点取走一个数直至取完。从第二次操作开始，每次操作你将会获得的分数为：上一次取走的数的本次取的数次方，对 998244353 取模。

求分数最大值。

有多测。

思路分析

首先，通过观察 n 的范围，可以确定，正解应该是 O(n^2) 的。于是，我们开始查找算法。

爆搜（你试试看），时间复杂度 2^n，可以试着算一下 2^{1000} 是多少。这种方法，绝对超时。

然后，求区间值的算法只剩下 dp 了。于是，开始 dp。

俗话说得好，dp 分三步。

  1. 设置状态（就是你这个 dp 数组表示什么，不然你都不知道在干什么）。

    显然，一开始想，dp_i 设为 1 \sim i 的最大值。很明显，这样只能顾及到从右边取的方案，排除。

    再加一维，很自然想到区间 dp。设置 dp_{i,j} 表示 i \sim j 的最大值。但是这样也有问题。即，你虽然能够转移了，但是上一次是在左边还是右边开始的，是个问题，解决不了。

    终于，状态表示出来了，设 dp_{i,j,0} 为 i \sim j 且从左端开始取的最大值，dp_{i,j,1} 即为 i \sim j 且从右端开始取的最大值。

  2. 推转移式（听起来高大上，实际上就是列举出所有可以到达这个状态的状态）

    很明显，如果是 dp_{i,j,0}，那么之前就是 dp_{i+1,j,0/1}，即上一个区间，左右都可以取。枚举即可。而 dp_{i,j,1} 同理。当然，还需要加上一个得分。不过，这里就需要用到快速幂了，不然会爆掉。

  3. 设置初始值（其实就是最基本的状态）

    本来，应该设 dp_{i,i,0/1} 的，因为它没法向下转移了。但是由于这里只有一个数，所以答案为 0，无需初始化。（当然有一些题目的初始值很麻烦，不要小看它）

好了，思路已经推出来了，如果还有不懂，看代码吧（或者私信）。

代码实现

就注意两点：

多测不清空，亲人两行泪！！！

不开 long long 见祖宗！！！

#include<bits/stdc++.h>
using namespace std;
//不开long long见祖宗 
#define int long long
int t,n,a[1010],dp[1010][1010][2],modd=998244353;
//快速幂，这里不讲了，可以去看模板，有很多人讲 
int fast_pow(int a,int b,int c){
    if(a==0&&b==0) return 0;
    int x,y,m=1;
    y=a,x=b;
    while(b){
        if(b%2){
            m=m*a%c;
        }
        a=a*a%c;
        b/=2;
    }
    return m;
}
signed main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        //注意，千万要清空 
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) dp[i][j][0]=dp[i][j][1]=0;
        }
        //dp部分 
        for(int len=1;len<n;len++){
            for(int i=1;i+len<=n;i++){
                int j=i+len;
                //转移。此时第一个是选左边，因此加上的分数应该是a[i]的a[i+1]或a[j]次方（根据情况） 
                dp[i][j][0]=max(dp[i+1][j][0]+fast_pow(a[i],a[i+1],modd),dp[i+1][j][1]+fast_pow(a[i],a[j],modd));
                //第一个选右边同理 
                dp[i][j][1]=max(dp[i][j-1][0]+fast_pow(a[j],a[i],modd),dp[i][j-1][1]+fast_pow(a[j],a[j-1],modd));
            }
        }
        //比较从左边取和从右边取的较大值 
        cout<<max(dp[1][n][0],dp[1][n][1])<<endl;
    }
    return 0;
}