CF1178 F1 Short Colorful Strip
2019-08-16 07:51:44来源:博客园 阅读 ()
CF1178 F1 Short Colorful Strip
题目链接
题意
有个长度为\(m\)公分的布,要在上面每公分都染上颜色,整块布染恰好\(n(n=m)\)种颜色。颜色标号从\(1\)到\(n\)。染色需遵循:
1.从颜色\(1\)到颜色\(n\)依次,即必须先染标号小的颜色
2.每次可以染任意一个区间,但必须满足这个区间之前的颜色是相同的。
询问将这块布染成所给颜色的方案数。
solution
区间\(dp\)。
\(f[l][r]\)表示染好\([l,r]\)这个区间的方案数。\(g[l][r]\)表示最小的颜色最后单独染的方案数。
所以就有\(g[l][r] = f[l][t-1] \times f[t+1][r]\),(\(a[t]\)为区间\([l,r]\)中的最小值)
然后枚举一个\(k\)表示\([l,k]\)全染成最小颜色值的方案数。
那么就有\(f[i][j]=\sum\limits_{k=l}^{r-1}g[l][k]\times f[k+1][r]\)
最后\(f[1][n]\)即为答案。
code
/*
* @Author: wxyww
* @Date: 2019-07-21 09:01:13
* @Last Modified time: 2019-07-21 10:48:02
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 510,mod = 998244353;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int a[N],f[N][N],g[N][N];
int main() {
int n = read(),m = read();
for(int i = 1;i <= n;++i) a[i] = read();
a[0] = 1e9;
for(int i = 1;i <= n + 1;++i) g[i][i] = f[i][i] = f[i][i - 1] = g[i][i - 1] = 1;
for(int len = 2;len <= n;++len) {
for(int l = 1;l + len - 1 <= n;++l) {
int r = l + len - 1,t = 0;
for(int k = l;k <= r;++k) if(a[k] < a[t]) t = k;
f[l][r] = g[l][r] = 1ll * f[l][t - 1] * f[t + 1][r] % mod;
for(int k = l;k < r;++k) {
f[l][r] = (f[l][r] + 1ll * g[l][k] * f[k + 1][r] % mod) % mod;
}
}
}
cout<<f[1][n];
return 0;
}
原文链接:https://www.cnblogs.com/wxyww/p/CF1178F1.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:7.19考试总结
下一篇:二分法(一):二分法的基本思想
- C语言数据类型 2018-06-18
- 网页title添加图标 2018-06-18
- spfa 2018-06-17
- POJ 2001 Shortest Prefixes 2018-06-17
- HDU 6035---Colorful Tree(树形DP) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash