2021牛客NOIP提高组OI赛前模拟赛第二场T2——牛牛和数组操作（区间dp）

• description
• solution
• code

【题目描述】
有n + 2个整数a0, a1, . . . , an, an+1， a0 = an+1 = 0。你需要做确切地n次操作，每次
操作为以下形式：
选择一个整数x满足ax ≠ 0，使得ax = 0，令 l = max i < x , a i = 0 ( i ) , r = min i > x , a i = 0 ( i ) l=text{max}_{ix,a_i=0}(i) l=maxix,ai​=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 ≤ n ≤ 2000 , 1 ≤ a i ≤ n 1le nle 2000, 1le a_ile n 1≤n≤2000,1≤ai​≤n

设第一个操作的人编号为 x x x，则在 x x x被操作后， [ 1 , x − 1 ] [1,x-1] [1,x−1]和 [ x + 1 , n ] [x+1,n] [x+1,n]的区间操作就互不影响了

因此可以考虑区间 d p dp dp

设 f l , r f_{l,r} fl,r​为对区间 [ l , r ] [l,r] [l,r]操作的最小代价， g l , r g_{l,r} gl,r​为对区间 [ l , r ] [l,r] [l,r]操作最小代价的不同操作序列数量

枚举区间操作点 i i i，则 f l , r = min { f l , i − 1 + f i + 1 , r } , g l , r = g l , i − 1 ∗ g i + 1 , r ∗ ( r − l i − l ) f_{l,r}=text{min}{f_{l,i-1}+f_{i+1,r}},g_{l,r}=g_{l,i-1}*g_{i+1,r}*binom{r-l}{i-l} fl,r​=min{fl,i−1​+fi+1,r​},gl,r​=gl,i−1​∗gi+1,r​∗(i−lr−l​)

虽然区间 d p dp dp是从小到大，但实际上我们的操作是将大区间操作某个点切割成若干小区间

到这里为止，时间复杂度就是 O ( n 3 ) O(n^3) O(n3)，但是评测机上面跑得飞快，就人间迷惑行为？？

以下是不清楚题解的“正解” ：实际上，贪心的想法，操作区间的最大值肯定是最优秀的，因此只需要枚举区间最大值即可。同时对于一段区间 [ l , r ] [l,r] [l,r]，如果存在 a i = a i + 1 = max ( a j , j ∈ [ l , r ) ) a_i=a_{i+1}=text{max}Big(a_j,jin[l,r)Big) ai​=ai+1​=max(aj​,j∈[l,r))则此时 i , i + 1 i,i+1 i,i+1的选择顺序没有影响，因此当碰到连续两个最大值出现时，直接将区间划分为两段，最大值不连续则仍直接枚举最大值，从而时间复杂度为 O ( n 3 2 ) O(n^{frac{3}{2}}) O(n23​)

#include 
#include 
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( "%lldn", g[1][n] );
	return 0;
}