BZOJ2958 序列染色(动态规划)
2024-10-18 23:27:57
令f[i][0/1/2][0/1]表示前i位,不存在满足要求的B串和W串/存在满足要求的B串不存在W串/存在满足要求的B串和W串,第i位填的是B/W的方案数。转移时考虑连续的一段填什么。大讨论一波后瞎优化一波就成线性的了。k=1应该是要特判一下的不过数据里没有那就不管了。
成功的把这么短的题面都看错了一次。弱智dp写的心态爆炸。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 1000010
#define P 1000000007
int n,m,a[N],pre[N][],p[],f[N][][],delta[][];
void inc(int &x,int y){x+=y;if (x>=P) x-=P;}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj2958.in","r",stdin);
freopen("bzoj2958.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read(),m=read();
char c=getchar();while (c<'A'||c>'Z') c=getchar();
for (int i=;i<=n;i++)
{
a[i]=(c=='X')?:(c=='B'?:);
if (a[i]<) p[a[i]]=i;
pre[i][]=p[];pre[i][]=p[];
c=getchar();
}
a[]=;
f[][][]=f[][][]=;
delta[][]=(a[]!=),delta[][]=(a[]!=);
for (int i=;i<=n;i++)
{
f[i][][]=delta[][],f[i][][]=delta[][],f[i][][]=delta[][];
f[i][][]=delta[][],f[i][][]=delta[][],f[i][][]=delta[][];
inc(delta[][],f[i][][]);inc(delta[][],f[i][][]);inc(delta[][],f[i][][]);
inc(delta[][],f[i][][]);inc(delta[][],f[i][][]);inc(delta[][],f[i][][]);
if (pre[i+][]<i-m+)
{
inc(delta[][],(P-f[i-m+][][])%P);
inc(delta[][],f[i-m+][][]);
}
if (pre[i+][]<i-m+)
{
inc(delta[][],(P-f[i-m+][][])%P);
inc(delta[][],f[i-m+][][]);
}
if (a[i+]==) delta[][]=delta[][]=delta[][]=;
if (a[i+]==) delta[][]=delta[][]=delta[][]=;
}
cout<<(f[n][][]+f[n][][])%P;
return ;
}
最新文章
- [转]ExtJs基础--Html DOM、Ext Element及Component三者之间的区别
- Android探索之Service全面回顾及总结
- 第一章:java语言概述与开发环境
- 关于Javascript中的复制
- Java中HashMap案例
- Asset Catalog Creator Free 生成程序内图标的软件
- iOS 断网处理
- linux环境下java读取sh脚本并执行
- [转载] Redis系统性介绍
- Spring Data(二)查询
- Axure之动态面板:登录面板切换
- android 图形图像
- Linux 搜某个文件里关键字的上下500行到执行文件里
- java使用代理发post请求
- 为什么macos开机黑屏但是有声音?
- HADOOP1.X中HDFS工作原理
- 线程 Thread Runnable 守护线程 join MD
- 关闭IPV6
- go语言基础之结构体做函数参数 值传递和地址传递
- Rancher OS