题目描述

blablabla

算法1

动态规划

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;
int nums[N];
long long dp[N][201][3];

int main()
{
    int n;
    cin >> n;
    long long res = 0;
    for(int i = 0; i < n; i++)
        cin >> nums[i];
    if(nums[1] == 0)
        for(int i = 1; i < 201; i++)
        {
            if(nums[0] == 0)
            {
                dp[1][i][1] = 1;
                dp[1][i][2] = i-1;
            }
            else
            {
                dp[1][i][1] = (i == nums[0]);
                dp[1][i][2] = (i > nums[0]);
            }
        }
    else
    {
        if(nums[0] == 0)
        {
            dp[1][nums[1]][1] = 1;
            dp[1][nums[1]][2] = nums[1]-1;
        }
        else
        {
            dp[1][nums[1]][1] = (nums[1] == nums[0]);
            dp[1][nums[1]][2] = (nums[1] > nums[0]);
        }
    }

    for(int k = 2; k < n; k++)
    {
        if(nums[k] == 0)
        {
            for(int i = 1; i < 201; i++)
            {
                dp[k][i][1] = dp[k-1][i][0]+dp[k-1][i][1]+dp[k-1][i][2];
                for(int j = 1; j < i; j++)
                    dp[k][i][2] += (dp[k-1][j][0]+dp[k-1][j][1]+dp[k-1][j][2])%998244353;
                for(int j = i+1; j < 201; j++)
                    dp[k][i][0] += (dp[k-1][j][0]+dp[k-1][j][1])%998244353;
            }
        }
        else{
            int i = nums[k];
            dp[k][i][1] = dp[k-1][i][0]+dp[k-1][i][1]+dp[k-1][i][2];
            for(int j = 1; j < i; j++)
                dp[k][i][2] += dp[k-1][j][0]+dp[k-1][j][1]+dp[k-1][j][2];
            for(int j = i+1; j < 201; j++)
                dp[k][i][0] += dp[k-1][j][0]+dp[k-1][j][1];
        }
    }//cout << res << endl;
    for(int i = 1; i < 201; i++)
    {
        res += dp[n-1][i][0]+dp[n-1][i][1];
        res %= 998244353;
    }
    cout << res << endl;
}