企业网站代码怎么优化,上海前端,石家庄建设局,南召微网站开发牛牛和数组操作descriptionsolutioncodedescription
【题目描述】 有n 2个整数a0, a1, . . . , an, an1#xff0c; a0 an1 0。你需要做确切地n次操作#xff0c;每次 操作为以下形式#xff1a; 选择一个整数x满足ax ≠ 0#xff0c;使得ax 0#xff0c;令lmaxi…
牛牛和数组操作descriptionsolutioncodedescription
【题目描述】 有n 2个整数a0, a1, . . . , an, an1 a0 an1 0。你需要做确切地n次操作每次 操作为以下形式 选择一个整数x满足ax ≠ 0使得ax 0令lmaxix,ai0(i),rminix,ai0(i)l\text{max}_{ix,a_i0}(i),r\text{min}_{ix,a_i0}(i)lmaxix,ai0(i),rminix,ai0(i)此次操 作的花费为max(al, al1, . . . , ax-1) max(ax1. . . , ar-1, ar)牛币。 有多少不同的操作方式使得操作花费的牛币最少两种操作不同当且仅当两种操 作的操作序列不同。 答案对998244353取模。 友情提示本题正解复杂度很大常数很小。 【输入格式】 第一行一个整数n。 第二行n个整数a1, a2, . . . , an。 【输出格式】 输出一行一个整数表示答案。 【样例 1 输入】 5 2 2 2 1 1 【样例 1 输出】 40 【样例 2 输入】 88 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 【样例 2 输出】 235381964 【数据范围】
1≤n≤2000,1≤ai≤n1\le n\le 2000, 1\le a_i\le n1≤n≤2000,1≤ai≤n
solution
设第一个操作的人编号为xxx则在xxx被操作后[1,x−1][1,x-1][1,x−1]和[x1,n][x1,n][x1,n]的区间操作就互不影响了
因此可以考虑区间dpdpdp
设fl,rf_{l,r}fl,r为对区间[l,r][l,r][l,r]操作的最小代价gl,rg_{l,r}gl,r为对区间[l,r][l,r][l,r]操作最小代价的不同操作序列数量
枚举区间操作点iii则fl,rmin{fl,i−1fi1,r},gl,rgl,i−1∗gi1,r∗(r−li−l)f_{l,r}\text{min}\{f_{l,i-1}f_{i1,r}\},g_{l,r}g_{l,i-1}*g_{i1,r}*\binom{r-l}{i-l}fl,rmin{fl,i−1fi1,r},gl,rgl,i−1∗gi1,r∗(i−lr−l)
虽然区间dpdpdp是从小到大但实际上我们的操作是将大区间操作某个点切割成若干小区间
到这里为止时间复杂度就是O(n3)O(n^3)O(n3)但是评测机上面跑得飞快就人间迷惑行为
以下是不清楚题解的“正解” 实际上贪心的想法操作区间的最大值肯定是最优秀的因此只需要枚举区间最大值即可。同时对于一段区间[l,r][l,r][l,r]如果存在aiai1max(aj,j∈[l,r))a_ia_{i1}\text{max}\Big(a_j,j\in[l,r)\Big)aiai1max(aj,j∈[l,r))则此时i,i1i,i1i,i1的选择顺序没有影响因此当碰到连续两个最大值出现时直接将区间划分为两段最大值不连续则仍直接枚举最大值从而时间复杂度为O(n32)O(n^{\frac{3}{2}})O(n23)
code
#include cstdio
#include iostream
using namespace std;
#define int long long
#define mod 998244353
#define maxn 2005
int c[maxn][maxn], f[maxn][maxn], g[maxn][maxn], Max[maxn][maxn];
int a[maxn];
int n;signed main() {freopen( array.in, r, stdin );freopen( array.out, w, stdout );scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld, a[i] );for( int i 0;i n;i ) {c[i][0] c[i][i] 1;for( int j 1;j i;j )c[i][j] ( c[i - 1][j - 1] c[i - 1][j] ) % mod;}g[n 1][n] 1;for( int l n;l;l -- ) {g[l][l] g[l][l - 1] 1, Max[l][l] a[l];for( int r l 1;r n;r ) {f[l][r] 1e18;Max[l][r] max( Max[l][r - 1], a[r] );for( int i l;i r;i ) {int x Max[l][i - 1] Max[i 1][r] f[l][i - 1] f[i 1][r];int cnt g[l][i - 1] * g[i 1][r] % mod * c[r - l][i - l] % mod;if( x f[l][r] ) f[l][r] x, g[l][r] cnt;else if( x f[l][r] ) g[l][r] ( g[l][r] cnt ) % mod;}}}printf( %lld\n, g[1][n] );return 0;
}
