P10236 题解

· · 题解

P10236题解

前言：

黑润心有错夏令营讲了这道题，我本想抄题解的，结果发现看不懂前几篇，只能自己写一篇啦。

正文：

算法判断：

我们可以发现这个操作只能删去头和尾，所以无论经过多少次合法的操作，得到的数组一定是原串的子串。什么？连续？好！区间动态规划，启动！

状态定义：

我们定义 dp_{l,r,0} 为 [l,r] 序列下一个将删去最左边的数的最大得分，同理 dp_{l,r,1} 为 [l,r] 序列下一个将删去最右边的数的最大得分。

如何转移：

我们知道 [l,r,0/1] 一定是由 [l-1,r,0] 或 [l,r+1,1] 转移而来，转移是有得分的，如何计算得分？

计算得分：

举个栗子：

推出方程

我们现在就可以推出方程了：

dp_{i,j,0}=\max(dp_{i-1,j,0}+a_{i-1}^{a_i},dp_{i,j+1,1}+a_{j+1}^{a_i}) dp_{i,j,1}=\max(dp_{i-1,j,0}+a_{i-1}^{a_j},dp_{i,j+1,1}+a_{j+1}^{a_j})

得到答案

根据题意我们的答案是 \max(dp_{i,i,0},dp_{i,i,1}) 其中 i 为 1 到 n 的任意整数。

补充

我们现在把代码交了上去交了，啊？为什么不对？

对了！记得要用快速幂，还一定要特判 0^0=0。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod=998244353;
ll quickpow(ll x,ll y)
{
    if(x==0&&y==0)
    {
        return 0;//特判！！！ 
    }
    ll ans=1,p=x;
    while(y>0)
    {
        if(y&1)
        {
            ans=(ans*p)%mod;
        }
        p=(p*p)%mod;
        y>>=1;
    }
    return ans;
}
ll T,dp[1009][1009][2],a[1009],n; 
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(ll i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        memset(dp,0,sizeof(0));//多测清空 
        for(ll len=n;len>=1;len--)//按题目顺序枚举长度 
        {
            for(ll i=1;i<=n-len+1;i++)//枚举左右端点 
            {
                ll j=i+len-1;
                dp[i][j][0]=max(dp[i-1][j][0]+quickpow(a[i-1],a[i]),dp[i][j+1][1]+quickpow(a[j+1],a[i]));
                dp[i][j][1]=max(dp[i-1][j][0]+quickpow(a[i-1],a[j]),dp[i][j+1][1]+quickpow(a[j+1],a[j]));
            }
        }
        ll ans=0;
        for(ll i=1;i<=n;i++)//统计答案 
        {
            ans=max(ans,dp[i][i][0]);
            ans=max(ans,dp[i][i][1]);
        }
        cout<<ans<<endl;
    }
    return 0;
 }