CodeForces-1178F1 Short Colorful Strip 区间DP

摘要:
结合数据范围,我们可以认为染色方案的数量表示为具有间隔DP的相同颜色。限制:当给定的最终颜色被染色时,确定该间隔中的下一个颜色,即该间隔中最小值。你可以记住位置。此时,我们知道在枚举的染色间隔中只有一个点,因此和将被染色为其他颜色,因此整个间隔被分成四个部分,成为一个独立的子问题,所以我们可以使用namespacestd来DP[DP[l][r]=sum_{lleqileqp}sum_[pleqjleqr}DP[l][i-1]imesdp[i][p-1]imersdp[p+1][j]imestp[j+1][r]=]注意边界设置#includec;forc[i]=rd();fordp[i][i]=1;对于{for{intpos=l,l=0,R=0;forifpos=i;forL+=dp[l][i-1]*dp[i][pos-1]%MOD,l%=MOD;对于R+=dp[pos+1][i]*dp[i+1][l+len]%MOD;dp[l][l+len]=l*R%MOD;}}cout
CodeForces-1178F1 Short Colorful Strip 区间DP

题意

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

[1 leq nleq500,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_{pleq j leq r} dp[l][i - 1] imes dp[i][p - 1] imes dp[p + 1][j] imes dp[j + 1][r] \ = (sum_{l leq i leq p} dp[l][i - 1] imes dp[i][p - 1] )(sum_{p leq j leq r}dp[p+1][j] imes 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];
} 

免责声明:文章转载自《CodeForces-1178F1 Short Colorful Strip 区间DP》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇友盟官方文档《深入理解Java内存模型》读书总结下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

django的优缺点(非原创)

Django做了很多。使用它快速开发一些Web应用程序是很好的。因此,在一些人眼中,Django只不过是一种灵丹妙药,但对一些人来说,它也是一种毒药和剧毒。Django开发人员也讨论并试图支持SQLAlchemy,但最终放弃了。据估计,成本太高,很难与Django的其他模块集成。尽管Django的ORM不如SQLAlchemy强大,但它并不弱。Django的...

开源跳板机jumpserver的安装部署和使用详细教程及踩坑经验

安装篇jumpserver需要依赖于mysql数据库,python开发工具的支持,所以需要安装一系列软件。按照提示进行所有流程的安装,安装完成之后访问http://ip:8000端口即可登录到jumpserver。因为jumpserver会在被管理的后端主机上通过此处指定的管理用户来添加指定的用户和sudo权限:配置sudo授权,用于添加sudo授权。...

图论介绍(Graph Theory)

G-v具有比G更多的连通分支,因此v被称为G的截断点G-e具有比G多的连通分支。定理:连通图G,其中e是桥e不属于G的任何环有顶点u,v,使得任何路径u-v都通过e连通图G;而w是存储在顶点u,v处的割点,使得任意路径u-v通过w定义:顶点之间的距离x-y:所有x-y路径的最小长度。...

搭建我的世界服务器(史上最详细) java环境配置 ,免费内网穿透,家庭用电脑也欧克

服务器部署周末想要和好基友联机?这里有最简单的开服教程!最后打开我的世界输入服务器ip,和你自己在内网穿透网站设置的端口连接即可成功要想服务器稳定运行,要保证命令窗口和端口映射一直开着...

mongodb 占用内存及解决方法

解决方案是限制Swap的使用:[root@mongodb~]#Sysctl wvm。swap=0查看内存最常用的命令是空闲的:[root@mongodb~]#Free totalused freesharedbuff/cacheavailableEm:78250931925992443Swap:000当新手看到used列中的值太大而Free列中的数值太小时,...

ARM内核全解析,从ARM7,ARM9到Cortex-A7,A8,A9,A12,A15到Cortex-A53,A57

Cortex-A50是继Cortex-A15之后的又一重量级产品,将会直接影响到主流PC市场的占有率。ARM处理器架构发展●Cortex-A57、A53处理器Cortex-A53、Cortex-A57两款处理器属于Cortex-A50系列,首次采用64位ARMv8架构,意义重大,这也是ARM最近刚刚发布的两款产品。Cortex-A12架构图ARM表示Cort...