【Codeforces Round #518 (Div. 2) [Thanks, Mail.Ru!] D. Array Without Local Maximums】DP+滚动数组优化

D. Array Without Local Maximums

题意

$本来有一个n个数字的数组，数字大小从1到200$
$现在有些数字看不清了，但是只记得原数组有一种性质$
$a[2]>=a[1]$
$a[n?1]>=a[n]$
$a[i]<=max(a[i?1],a[i+1])2<=i<=n?1$

做法
$对于这个数据范围，很显然就能想到dp$
$定义DP状态为dp[i][j][k]$
$dp[i][j][0]表示第i个数为j而且小于前一个数的状态数$
$dp[i][j][1]表示第i个数为j而且等于前一个数的状态数$
$dp[i][j][2]表示第i个数为j而且大于前一个数的状态数$
$转移方程也很显然，只不过对于第二个位置的dp数组要特殊处理$
$而且需要滚动数组对dp进行前缀和优化$

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define dbg(x) cout<<#x<<" = "<<x<<endl
typedef long long ll;
const ll Mod = 998244353 ;
const int maxn = 1e5+10;
ll dp[maxn][201][3];
ll a[maxn];
ll sum1[maxn],sum2[maxn];
int main()
{
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);if(a[1]==-1){
    if(a[2]==-1){
    for(int j=1;j<=200;j++){
    dp[2][j][1]=1;dp[2][j][2]=j-1;}}else{
    dp[2][a[2]][1]=1;dp[2][a[2]][2]=a[2]-1;}}else{
    if(a[2]==-1){
    for(int j=a[1]+1;j<=200;j++){
    dp[2][j][2]=1;}dp[2][a[1]][1]=1;}else{
    if(a[1]==a[2]) dp[2][a[2]][1]=1;else if(a[1]<a[2])  dp[2][a[2]][2]=1;}}for(int j=1;j<=200;j++) sum1[j]=(sum1[j-1]+dp[2][j][0]+dp[2][j][1]+dp[2][j][2])%Mod;for(int j=200;j>=1;j--) sum2[j]=(sum2[j+1]+dp[2][j][0]+dp[2][j][1])%Mod;for(int i=3;i<=n;i++){
    if(a[i]!=-1){
    dp[i][a[i]][0]=sum2[a[i]+1];dp[i][a[i]][1]=(dp[i-1][a[i]][0]+dp[i-1][a[i]][1]+dp[i-1][a[i]][2])%Mod;dp[i][a[i]][2]=sum1[a[i]-1];}else{
    for(int j=1;j<=200;j++){
    dp[i][j][0]=(dp[i][j][0]+sum2[j+1])%Mod;dp[i][j][1]=(dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2])%Mod;dp[i][j][2]=(dp[i][j][2]+sum1[j-1])%Mod;}}for(int j=1;j<=200;j++) sum1[j]=(sum1[j-1]+dp[i][j][0]+dp[i][j][1]+dp[i][j][2])%Mod;for(int j=200;j>=1;j--) sum2[j]=(sum2[j+1]+dp[i][j][0]+dp[i][j][1])%Mod;}ll ans=0;for(int i=1;i<=200;i++){
    ans=(ans+dp[n][i][0]+dp[n][i][1])%Mod;}printf("%lld\n",ans);return 0;
}