ABC291D计数DP记忆化搜索倒搜

#include <stdio.h>
#include <string.h>
const int N=200050, mo=998244353;
int n, m, i, j, k, a[N][2], f[N][2];
int dfs(int k, int p){//填到第k个数，上一个状态为p
    if(k > n) return 1;//到最后也相邻不重复，可以计数
    if(~f[k][p]) return f[k][p];
    int s = 0;
    if(a[k][0] != a[k-1][p]) s += dfs(k+1, 0);
    if(a[k][1] != a[k-1][p]) s += dfs(k+1, 1);
    return f[k][p] = s%mo;
}//不翻转为0，之前是p，不相同才可以搜下去
int main(){
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d%d", &a[i][0], &a[i][1]);
    }
    memset(f, -1, sizeof(f));//a、b相同方案为0，用-1做默认值
    printf("%d\n", dfs(1, 0));
    return 0;
}