牛牛和數組操作

• description
• solution
• code

description

【題目描述】
有n + 2個整數a0, a1, . . . , an, an+1， a0 = an+1 = 0。你需要做確切地n次操作，每次
操作為以下形式：
選擇一個整數x滿足ax ≠ 0，使得ax = 0，令$l={\text{max}}_{i<x,a_i=0}(i),r={\text{min}}_{i>x,a_i=0}(i)$，此次操
作的花費為max(al, al+1+, . . . , ax-1) + max(ax+1. . . , 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\le n\le 2000,1\le a_i\le n$

solution

設第一個操作的人編號為$x$，則在$x$被操作后，$[1,x?1]$和$[x+1,n]$的區間操作就互不影響了

因此可以考慮區間$dp$

設$f_{l,r}$為對區間$[l,r]$操作的最小代價，$g_{l,r}$為對區間$[l,r]$操作最小代價的不同操作序列數量

枚舉區間操作點$i$，則$f_{l,r}=\text{min}\{f_{l,i?1}+f_{i+1,r}\},g_{l,r}=g_{l,i?1}?g_{i+1,r}?\left(\genfrac{}{}{0ex}{}{r?l}{i?l}\right)$

雖然區間$dp$是從小到大，但實際上我們的操作是將大區間操作某個點切割成若干小區間

到這里為止，時間復雜度就是$O(n^3)$，但是評測機上面跑得飛快，就人間迷惑行為？？

以下是不清楚題解的“正解” ：實際上，貪心的想法，操作區間的最大值肯定是最優秀的，因此只需要枚舉區間最大值即可。同時對于一段區間$[l,r]$，如果存在$a_i=a_{i+1}=\text{max}(a_j,j\in [l,r))$則此時$i,i+1$的選擇順序沒有影響，因此當碰到連續兩個最大值出現時，直接將區間劃分為兩段，最大值不連續則仍直接枚舉最大值，從而時間復雜度為$O(n^{\frac{3}{2}})$

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; }

總結

以上是生活随笔為你收集整理的2021牛客NOIP提高组OI赛前模拟赛第一场T2——牛牛和数组操作（区间dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。