[CF][DP][递推关系] codeforces 1068D Array Without Local Maximums

嗯。。。。果然还是那句话，直接上组合数学搞不定的组合数学，要么打表要么dp递推。

设dp[i][j][flag]表示前i数字，令最后一个数字为j时的方法数，其中flag==0表示第i-1个比第i个小，flag==1表示第i-1大于等于第i个，然后根据题目要求就是不能出现局部极大值，所以可以写出来递推式：① dp[i][j][0]=Σ(dp[i-1][k][0]+dp[i-1][k][1]) ,1<=k<j    ② dp[i][j][1]=dp[i-1][j][0]+Σdp[i-1][k][1],j<=k<=200 边界条件的话是单独考虑i==1的时候，特判算一下就可以了。这个方法是n*200个状态，每次转移再*200就是40000*n，太慢，观察到是求前缀/后缀和的形式，可以每一轮算完i之后维护一个presum[j][flag]，保存这一轮的前缀和，这样的话可以O(1)转移，复杂度就变成了n*200 。

主要的思考的点就在于在满足题目条件的约束下递推，加了一维状态表示之后问题就变得很简单了，所以推不出来的时候可以考虑加维（增加dp的信息量）
由于偷懒到处取模所以代码很慢吧。。。不过dp重要的是思想hhh

#include

using namespace std;
const int maxn=1e5+5;
const int mod=998244353;
const int INF=0x3f3f3f3f;
typedef long long LL;

int ori[maxn];
LL dp[maxn][205][2];
LL pre[205][2];



int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>ori[i];
    if(ori[1]==-1)
    {
        for(int i=1; i<=200; i++)
        {
            dp[1][i][0]=1;
            pre[i][0]=pre[i-1][0]+1;
        }
    }
    else
    {
        dp[1][ori[1]][0]=1;
        for(int i=1;i<=200;i++)
            pre[i][0]=pre[i-1][0]+dp[1][i][0];
    }
    for(int i=2; i<=n; i++)
    {
        if(ori[i]!=-1)
        {
            dp[i][ori[i]][0]=(pre[ori[i]-1][0]+pre[ori[i]-1][1])%mod;
            dp[i][ori[i]][1]=(dp[i-1][ori[i]][0]+pre[200][1]-pre[ori[i]-1][1])%mod;
            for(int j=1; j<=200; j++)
                pre[j][0]=(pre[j-1][0]+dp[i][j][0])%mod,pre[j][1]=(pre[j-1][1]+dp[i][j][1])%mod;
            continue;
        }
        for(int j=1; j<=200; j++)
        {
            dp[i][j][0]=(pre[j-1][0]+pre[j-1][1])%mod;
            dp[i][j][1]=(dp[i-1][j][0]+pre[200][1]-pre[j-1][1])%mod;

        }
        for(int j=1;j<=200;j++)
        {
            pre[j][0]=(pre[j-1][0]+dp[i][j][0])%mod;
            pre[j][1]=(pre[j-1][1]+dp[i][j][1])%mod;
        }
    }
    cout<<(pre[200][1]%mod+mod)%mod;
    return 0;
}