nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

cf518D

链接

https://codeforces.com/contest/1068/problem/D

题意

        长度为n(1e5)的数组，值域为1到200，且每个数的旁边必有一个大于等于它的数。有些数字被擦掉了，问共有几种填充的方案满足上述要求。

题解

        dp[i][j][0] 填完了前i位且第i位填j,且第i位小于i-1位
        dp[i][j][1] 填完了前i位且第i位填j,且第i位等于i-1位
        dp[i][j][2] 填完了前i位且第i位填j,且第i位大于i-1位
        
        dp[i][j][0] <--- dp[i-1][k][0],dp[i-1][k][1],              j<k
        dp[i][j][1] <--- dp[i-1][k][0],dp[i-1][k][1],dp[i-1][k][2] j=k
        dp[i][j][2] <--- dp[i-1][k][0],dp[i-1][k][1],dp[i-1][k][2] j>k