bzoj1996

区间dp

其实我们发现对于一段区间我们是这样构造的，每次我们会向两端放数，这样就有四种情况，且必须满足题意，初值是dp[i][i][0]=1,因为第一个人只有一种放法，不分左右。其实看见dp[i][i][0/1]=1时答案是16就改初值

#include<bits/stdc++.h>

using namespace std;

const int N = , mod = ;

int n;

int h[N], dp[N][N][];

void up(int &x, int d)

{

    x = (x + d) % mod;

}

int dfs(int l, int r, int f)

{

    if(l == r) return f;

    if(dp[l][r][f] != -) return dp[l][r][f];

    int &ret = (dp[l][r][f] = );

    if(f == )

    {

        if(h[l] < h[l + ]) up(ret, dfs(l + , r, f));

        if(h[l] < h[r]) up(ret, dfs(l + , r, f ^ ));

    }

    else

    {

        if(h[r] > h[r - ]) up(ret, dfs(l, r - , f));

        if(h[r] > h[l]) up(ret, dfs(l, r - , f ^ ));

    }

    return ret;

}

int main()

{

    memset(dp, -, sizeof(dp));

    scanf("%d", &n);

    for(int i = ; i <= n; ++i) scanf("%d", &h[i]);

    printf("%d\n", (dfs(, n, ) + dfs(, n, )) % mod);

    return ;

}

巴特西

bzoj1996

最新文章

热门文章