CodeForces-1178F1 Short Colorful Strip 区间DP

CodeForces-1178F1 Short Colorful Strip 区间DP

题意

给定\(0-n\) 一共 \(n+1\)种颜色,现有\(m\)段初始时刻颜色都是0的纸,对这张纸的段进行操作,第\(i\)次操作会选择第\(l\)段到第\(r\)段纸进行区间染色,条件是这段此时必须为同种颜色,染为\(i\)。给出最终的每一段的颜色,问共有多少种染色方案,注意本题中\(n = m\)且每种颜色都会在最终的段中出现

\[1 \leq n\leq500,n = m\\ 1 \leq c_i \leq n \]

分析

做\(CF\)题自然要先挖掘性质,注意到此题的性质在于\(n = m\) ,染色时必须选择相同的颜色染色,这说明我们不能跨区间染色,且填某个颜色时的区间一定包含最终的那个位置。

再结合数据范围 想到用区间DP来做

令\(dp[l][r]\)表示\([l,r]\)为同一种颜色时的染色方案数,限制:题给的最终颜色

因此染色时,对这个区间的下一个颜色是确定的,也就是这段中最小值,不妨记位置作\(p\),此时枚举\(p\)的染色区间\([i,j]\),我们知道最终只有\(p\)一个点,因此\([i,p - 1]\)和\([p+1,j]\)都会被染成其他颜色,于是整个区间\([l,r]\)就被分为四个部分,成为了独立的子问题,于是可以DP了

\[dp[l][r] = \sum_{l \leq i \leq p}\sum_{p\leq j \leq r} dp[l][i - 1]\times dp[i][p - 1] \times dp[p + 1][j] \times dp[j + 1][r] \\ = (\sum_{l \leq i \leq p} dp[l][i - 1] \times dp[i][p - 1] )(\sum_{p \leq j \leq r}dp[p+1][j] \times dp[j + 1][r]) \]

代码

注意边界的设置

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll rd(){
	ll x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x;
}

const ll MOD = 998244353;

int dp[505][505];


int main(){
	int n = rd();
	int m = rd();
	vector<int> c(n + 1,0);
	for(int i = 1;i <= n;i++)
		c[i] = rd();
	for(int i = 1;i <= n + 1;i++)
		dp[i][i - 1] = dp[i][i] = 1;
	for(int len = 1;len < n;len++){
		for(int l = 1;l + len <= n;l++){
			int pos = l,L = 0,R = 0;
			for(int i = l;i <= l + len;i++)
				if(c[i] < c[pos]) pos = i;
			for(int i = l;i <= pos;i++)
				L += (ll)dp[l][i - 1] * dp[i][pos - 1] % MOD,L %= MOD;
			for(int i = pos;i <= l + len;i++) 
				R += (ll)dp[pos + 1][i] * dp[i + 1][l + len] % MOD,R %= MOD;
			dp[l][l + len] = (ll) L * R % MOD;
		}
	}
	cout << dp[1][n];
} 
上一篇:为什么 Java 的 +、-、*、*/+复合分配操作不需要转换?| Java Debug 笔记


下一篇:Android N Data Setup & Disconnect For Short Connection