打卡信奥刷题（3430）用C++实现信奥题 P10236 [yLCPC2024] D. 排卡-拓冰建站

P10236 [yLCPC2024] D. 排卡

题目背景

经过千辛万苦，扶苏终于到达了机厅。但是她很快发现机厅排起了大 b 队~~（不是省选的 B 队）~~。

舞萌玩家们在人多的时候经常采取排卡的方式决定谁下一个上机。因为人实在是太多了，他们在排卡的时候，便注意到了卡上的编号。

他们向扶苏提了一个问题，你能解决吗？

题目描述

扶苏有一个双端队列aaa。这个队列与计算机科学中队列的概念类似，不同的是，这个队列既可以从队列头读取和弹出元素，也可以在队列尾部读取和弹出元素，因此被称为『双端队列』。

这个队列中有nnn个数。扶苏将通过nnn次操作构造一个长度为nnn的序列bbb，第iii（1≤i≤n1 \leq i \leq n1≤i≤n）次操作会可以进行如下两个过程之一：

令bib_ibi为aaa的队列头，并在aaa的头部弹出一个元素。
令bib_ibi为aaa的队列尾，并在aaa的尾部弹出一个元素。

我们定义一个数对(i,j)(i, j)(i,j)的得分为：

score(i,j)=ij mod 998244353\mathrm{score}(i,j) = i^j \bmod 998244353score(i,j)=ijmod998244353

即iii的jjj次幂对998244353998244353998244353取余数的结果。特别的，在本题中我们规定00=00^0 = 000=0。

现在，扶苏想用最优的策略构造bbb序列，最大化如下式子的值：

∑i=1n−1score(bi,bi+1)\sum_{i = 1}^{n - 1} \mathrm{score}(b_i, b_{i + 1})i=1∑n−1score(bi,bi+1)

即bbb所有相邻两项按原顺序计算的得分之和。

注意，我们仅在计算一个数对的时候将得分对998,244,353998,244,353998,244,353取模，在计算求和时不再将这个和取余。

输入格式

本题单个测试点内有多组测试数据。第一行是一个正整数，表示数据组数TTT。对每组数据：

第一行是一个整数nnn（2≤n≤1032 \leq n \leq 10^32≤n≤103），表示序列的长度。
第二行有nnn个整数a1,a2,…ana_1, a_2, \dots a_na1,a2,…an（0≤ai<998,244,3530 \leq a_i < 998,244,3530≤ai<998,244,353），按从头到尾的顺序表示队列aaa里每个数字的值。

数据保证单个测试点内nnn的和不超过10310^3103。

输出格式

对每组测试数据，输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

2 5 5 3 1 4 2 6 6 5 1 4 2 3

输出 #1

1168 15655

C++实现

#include<bits/stdc++.h>usingnamespacestd;#definelllonglongll mod=998244353;llquickpow(ll x,ll y){if(x==0&&y==0){return0;//特判！！！}ll ans=1,p=x;while(y>0){if(y&1){ans=(ans*p)%mod;}p=(p*p)%mod;y>>=1;}returnans;}ll T,dp[1009][1009][2],a[1009],n;intmain(){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;}return0;}