【[POI2006]MIS-Teddies】

出去颓废还水了道题。。。

传送门

这是一道dp。

设$f[i][a][b][c][y][x]$表示dp到第i个熊，第一种熊用了a个，第二种用了b个，第三种用了c个，那么自然第四种用了i-a-b-c个，最后一只熊是第x种，倒数第二只是第y种的方案数。

把每一位都枚举出来，再枚举倒数第三只熊判断合法就可以转移了。

因为转移只会用到i和i-1，所以第一维可以滚动掉，还有，前两只熊要自己用手填出来。

以及判断合法的方式借鉴了另一篇题解。

#include<cmath>
#include<cstdio>
#include<iostream>
#define mod 1000000
using namespace std;
int f[2][39][39][39][4][4];
int u[4],ans,p[4][4];
int main(){
//	freopen("3448.in","r",stdin);
//	freopen("my.out","w",stdout);
    scanf("%d%d%d%d",&u[0],&u[1],&u[2],&u[3]);
    int n=u[0]+u[1]+u[2]+u[3],o,d;
    if (n<2){
        puts("1");
        return 0;
    }
    p[0][0]=p[0][2]=1;p[0][1]=p[0][3]=-1;
    p[1][0]=p[1][1]=1;p[1][2]=p[1][3]=-1;
    for (int i=0; i<=3; i++)
        for (int j=0; j<=3; j++){
            if (i==j&&u[i]<2) continue;
            if (i==0&&u[i]){
                if (j==0&&u[j]) f[0][2][0][0][0][0]++;
                if (j==1&&u[j]) f[0][1][1][0][0][1]++;
                if (j==2&&u[j]) f[0][1][0][1][0][2]++;
                if (j==3&&u[j]) f[0][1][0][0][0][3]++;
            }
            if (i==1&&u[i]){
                if (j==0&&u[j]) f[0][1][1][0][1][0]++;
                if (j==1&&u[j]) f[0][0][2][0][1][1]++;
                if (j==2&&u[j]) f[0][0][1][1][1][2]++;
                if (j==3&&u[j]) f[0][0][1][0][1][3]++;
            }
            if (i==2&&u[i]){
                if (j==0&&u[j]) f[0][1][0][1][2][0]++;
                if (j==1&&u[j]) f[0][0][1][1][2][1]++;
                if (j==2&&u[j]) f[0][0][0][2][2][2]++;
                if (j==3&&u[j]) f[0][0][0][1][2][3]++;
            }
            if (i==3&&u[i]){
                if (j==0&&u[j]) f[0][1][0][0][3][0]++;
                if (j==1&&u[j]) f[0][0][1][0][3][1]++;
                if (j==2&&u[j]) f[0][0][0][1][3][2]++;
                if (j==3&&u[j]) f[0][0][0][0][3][3]++;
            }
        }
    for (int i=3; i<=n; i++){
        o=i%2;
        for (int a=0; a<=u[0]; a++)
        for (int b=0; b<=u[1]; b++)
        for (int c=0; c<=u[2]; c++){
            if (a+b+c<i-u[3]) continue;
            d=i-a-b-c;
            for (int x=0; x<=3; x++)
            for (int y=0; y<=3; y++){
            f[o][a][b][c][y][x]=0;
            for (int z=0; z<=3; z++){
                if(abs(p[0][x]+p[0][y]+p[0][z])==3||
                   abs(p[1][x]+p[1][y]+p[1][z])==3) continue;
                if (x==0&&a)
                    (f[o][a][b][c][y][x]+=f[o^1][a-1][b][c][z][y])%=mod;
                if (x==1&&b)
                    (f[o][a][b][c][y][x]+=f[o^1][a][b-1][c][z][y])%=mod;
                if (x==2&&c)
                    (f[o][a][b][c][y][x]+=f[o^1][a][b][c-1][z][y])%=mod;
                if (x==3&&d)
                    (f[o][a][b][c][y][x]+=f[o^1][a][b][c][z][y])%=mod;
            }
            }
        }
    }
    o=n%2;
    for (int i=0; i<=3; i++)
        for (int j=0; j<=3; j++){
            (ans+=f[o][u[0]][u[1]][u[2]][i][j])%=mod;
//			printf("%d %d: %d\n",i,j,f[o][u[0]][u[1]][u[2]][i][j]);
        }
    printf("%d\n",ans);
    return 0;
}