题意:

n<=1e5

思路:卡内存

dp[i][j][k]表示当前第i个数字为j,第i-1个数字与第i个之间大小关系为k的方案数(a[i-1]<a[i],=,>)

转移时使用前缀和和后缀和加速

如此简单的DP居然没有写出来,还想复杂了……

 #include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair
#define N 100010
#define M 200
#define MOD 998244353
#define eps 1e-8
#define pi acos(-1) ll dp[N][M+][],tmp;
int a[N]; int main()
{
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=M;i++)
{
if(a[]==-||i==a[]) dp[][i][]=;
else dp[][i][]=;
}
tmp=;
for(int i=;i<=n;i++)
{
for(int j=;j<=M;j++)
{
if(a[i]==-||j==a[i]) dp[i][j][]=(dp[i-][j][]+dp[i-][j][]+dp[i-][j][])%MOD;
else dp[i][j][]=;
} tmp=;
for(int j=;j<=M;j++)
{
if(a[i]==-||j==a[i]) dp[i][j][]=tmp;
else dp[i][j][]=;
tmp=(tmp+dp[i-][j][]+dp[i-][j][]+dp[i-][j][])%MOD;
} tmp=;
for(int j=M;j>=;j--)
{
if(a[i]==-||j==a[i]) dp[i][j][]=tmp;
else dp[i][j][]=;
tmp=(tmp+dp[i-][j][]+dp[i-][j][])%MOD;
}
}
ll ans=;
for(int i=;i<=M;i++) ans=(ans+dp[n][i][]+dp[n][i][])%MOD;
printf("%lld\n",ans);
return ;
}

最新文章

  1. JavaScript 嵌套 书名号 查询
  2. iOS——使用StroryBoard页面跳转及传值
  3. Node.js 手册查询-5-Ejs 方法
  4. Asp.net Vnext ModelBinding
  5. About TI CC3000 Wifi
  6. linq to sql 增删改查
  7. 接口(工厂模式&amp;代理模式)
  8. 更改web project 访问项目名称
  9. Bootstrap入门(八)组件2:下拉菜单
  10. 《java入门第一季》之面向对象(形式参数和返回值问题的深入研究3)
  11. springboot~内嵌redis的使用
  12. MemCache详细解读(转)
  13. it入门之:学会使用Git 分布式版本控制工具
  14. linux公社
  15. 【枚举】珠心算测验[c++]
  16. 顶级项目孵化的故事系列——Kylin的心路历程【转】
  17. java操作hbase1.3.1的增删改查
  18. CSS学习摘要-层叠和继承
  19. 20165302 ch02 课下作业
  20. 用NI的数据采集卡实现简单电子测试之3——绘制二极管V-I特性曲线图

热门文章

  1. SpringMVC URL模板模式映射
  2. find cat sed awk 简单组合使用
  3. CentOS下安装php gd库报错Error: php56w-common conflicts with php-common-5.3.3-48.el6_8.x86_64
  4. CodeForces 651B
  5. IIC如何释放数据总线? 为什么=1就是释放?
  6. HDU:2594-Simpsons’ Hidden Talents
  7. 动态规划:HDU2844-Coins(多重背包的二进制优化)
  8. [BZOJ1010]玩具装箱toy(斜率优化)
  9. HDU1272小希的迷宫
  10. 9、python中的控制流