枚举第一格放不放
之后递推即可
然而我写的什么鬼?
- #include <cstdio>
- const int MAXN=10111;
- int N;
- int Num[MAXN];
- long long DP[MAXN][4][4][4];
- int main(){
- scanf("%d", &N);
- for(int i=1;i<=N;++i) scanf("%d", &Num[i]);
- DP[2][1][1][0]=1L;
- DP[2][0][0][0]=1L;
- for(int i=2;i<=N;++i){
- for(int a=0;a<=3;++a){
- for(int b=0;b<=3;++b){
- for(int c=0;c<=3;++c){
- if(DP[i][a][b][c]==0LL) continue;
- if(a==Num[i-1]){
- DP[i+1][b][c][0]+=DP[i][a][b][c];
- }
- else if(a==Num[i-1]-1){
- DP[i+1][b+1][c+1][0]+=DP[i][a][b][c];
- }
- }
- }
- }
- }
- long long ANS=0LL;
- for(int b=0;b<=3;++b)
- for(int c=0;c<=3;++c){
- ANS+=DP[N+1][Num[N]][b][c];
- }
- printf("%lld\n", ANS);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2619557.html