[JXOI2017]数列
一个不太一样的做法
当\(A_{i-1}=x\),称\(A_1\)到\(A_{i-2}\)中大于等于\(A_{i-1}\)的最小值\(R\)为上界,\(A_1\)到\(A_{i-2}\)中小于等于\(A_{i-1}\)的最大值\(L\)为下界。对于一组\((L,R,x)\)显然有\(L\leq x\leq R\),我们下一个能填的数也只能在这个范围内。
当我们\(A_i=y\)的时候,考虑新的上下界分别是谁。
当\(x\leq y\leq R\)的时候,显然小于等于\(y\)中最大的是\(x\),大于等于\(y\)中最大的是\(R\),所以新的下界是\(x\),上界\(R\),三元组变成了\((x,R,y)\)
当\(L\leq y< x\)的时候,新的上界是\(x\),下界是\(L\),三元组变成了\((L,x,y)\)
到这里我们就可以写一个dp了,设\(f_{i,j,k,p}\)表示填了\(i\)个数,末尾三元组的状态是\((j,k,p)\),转移的时候枚举下一位填什么推出下一个三元组即可。状态数是\(O(nr_i^3)\),转移是\(O(r_i)\)的,复杂度是\(O(nr_i^4)\)不是很能接受
再观察一下这个dp的转移,发现它非常别致,我们枚举下一位填的数\(y\)
当\(p\leq y\leq k\),\(f_{i,j,k,p}\)向\(f_{i+1,x,k,y}\)转移,这个转移和\(j\)这一维没有关系
当\(j\leq y< p\),\(f_{i,j,k,p}\)向\(f_{i+1,j,x,y}\)转移,这个转移和\(k\)这一维没有关系
考虑一下是否可以去掉一维,上下界中只保存一个能否进行转移
显然是可以的,设\(dp_{i,j,k}\)表示当前填了\(i\)个数,上/下界为\(j\),末尾填的数为\(k\)。我们强行规定当\(k\leq j\)的时候,\(j\)为上界;当\(k>j\)的时候,\(j\)为下界
即对于原来的\(f_{i,j,k,p}\)拆分成了两个状态\(dp_{i,j,p}\)和\(dp_{i,k,p}\),这两个状态各自完成\(f_{i,j,k,p}\)的一部分转移。其中\(dp_{i,j,p}\)负责\(j\leq y<p\)的转移;\(dp_{i,k,p}\)负责\(p\leq y\leq k\)的转移。注意转移之后得到的仍旧是一个完整的上下界都有的状态,我们还是要把这个状态拆分一下。
转移的时候还是枚举下一位填什么数,根据填的数推出转移的状态即可。注意当一下位填的数和上下界相等时,新的上下界就固定了。
这样的状态数就变成了\(O(nr_i^2)\),复杂度是\(O(nr_i^3)\),不知道为什么跑的比较快,luogu最优解,loj位列rk3
代码
#include<bits/stdc++.h>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=155;
const int mod=998244353;
inline int qm(int x) {return x>=mod?x-mod:x;}
int h[55],n,o,R,dp[2][maxn][maxn];
int main() {
n=read();for(re int i=1;i<=n;i++) h[i]=read(),R=max(R,h[i]);R++;
for(re int i=1;i<=h[2];++i)
for(re int j=1;j<=h[1];++j) {
if(j>=i) {if(i!=j) dp[0][i][0]++;}
else dp[0][i][R]++;
dp[0][i][j]++;
}
for(re int i=3;i<=n;i++,o^=1) {
memset(dp[o^1],0,sizeof(dp[o^1]));
for(re int j=1;j<=h[i-1];j++)
for(re int k=0;k<=R;++k) {
if(!dp[o][j][k]) continue;
if(k<j) {
for(re int p=k;p<j;p++)
if(p<=h[i]&&p>0) {
if(p==k) {
dp[o^1][p][p]=qm(dp[o^1][p][p]+dp[o][j][k]);
continue;
}
dp[o^1][p][k]=qm(dp[o^1][p][k]+dp[o][j][k]);
dp[o^1][p][j]=qm(dp[o^1][p][j]+dp[o][j][k]);
}
}
else {
for(re int p=j;p<=k;++p)
if(p<=h[i]&&p>0) {
if(p==j||p==k) {
dp[o^1][p][p]=qm(dp[o^1][p][p]+dp[o][j][k]);
continue;
}
dp[o^1][p][j]=qm(dp[o^1][p][j]+dp[o][j][k]);
dp[o^1][p][k]=qm(dp[o^1][p][k]+dp[o][j][k]);
}
}
}
}
int ans=0;
for(re int i=1;i<=h[n];++i)
for(re int j=i;j<=R;++j) ans=qm(ans+dp[o][i][j]);
return !printf("%d\n",ans);
}
最新文章
- RHEL6.3系统安装
- QT编译时 cc1plus进程占用大量内存卡死问题解决
- UITableView使用
- MAT-Java内存分析工具
- opencv1-安装及资料
- Ubuntu14.04下jdk的安装
- jQuery积累
- MySQL 死锁问题分析
- web测试特别点
- ViewState
- Python之Fabric模块
- 从客户端(content=";<;span class=";Apple-s...";)中检测到有潜在危险的 Request.Form 值。
- PAT - IO-01. 表格输出(5)
- Redisql: the lightning fast data polyglot【翻译】 - Linvo's blog - 博客频道 - CSDN.NET
- 【转】HTTP长连接与短连接(2)
- STM32CubeMX GPIO的使用
- SE6新特性之集合Set、Map、WeakSet和WeakMap详解
- [Linux]systemd和sysV
- 【POJ3613】Cow Relays 离散化+倍增+矩阵乘法
- 零基础学python-7.2 字符串常量
热门文章
- Linux中通过grep命令检索文件内容和指定内容前后几行
- [Fw]初探linux中断系统(1)
- MVC的布局页,视图布局页和分布页的使用
- 配置进程外Session 同时解决一个奇怪的BUG 因为SQLserver 服务器名不是默认的.或者localhost而引发的一系列问题
- linux 用户空间与内核空间——高端内存了解
- GitHub区域和工作流程
- 割点的tarjan算法模板
- python函数参数*args **kwargs
- 进程调试--进程启动VS自动附加
- 【leetcode】997. Find the Town Judge