[HDOJ3545 Board Coloring]【动态规划】【四维求和】★★

【题目大意】
给定一个4*n的矩阵a[i,j]。(1<=i<=4 1<=j<=n)你要在里面填0~255的数字。
然后使得填了以后满足以下约束：
1：a[i,j]>=a[i,j-1]
2：对于一些给定了限制(i,j,i’,j’)，必须满足a[i,j]=a[i’,j’]。
【算法分析】
非常非常好的题目，没有涉及到什么高深的算法，但是非常巧妙，对于锻炼思维能力有很好的效果。
令F[p[1]][p[2]][p[3]][p[4]]表示现在涂完颜色c，然后第i列涂到p[i]时的方案数。
然后很容得出F[p[1]][p[2]][p[3]][p[4]]=Sum{F[c-1][p[1]’][p[2]’][p[3]’][p[4]’]}。
其中p[i]’<=p[i]。
然后对于那些相等限制，就是假如某个状态(p[i]但是这个求和还是不太简单。
一开始我搞了3个辅助数组一起求T_T。。。
后来猛然发现本质就是在“固定”其它3个位，只留现在这个位来动。然后就想到一个一个位顺着弄。
就变成现在程序这样子。
实际上是不需要滚动数组的。因为我们每次求出的都是下一次所需要的原数组。
【其它】1Y
【Record】时间跑成第一了。可能因为其它人大多用了滚动数组吧。
【CODE】
#include #include #include const int N=16;
const int Mod=100000;
int n,m;
int F[N][N][N][N];
int v[N][N][N][N];

void init(){
     memset(v,0,sizeof(v));
     scanf("%d%d",&n,&m);
     int i,p[5],x1,y1,x2,y2;
     for (i=1;i<=m;i++){
       scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
       for (p[1]=0;p[1]<=n;p[1]++)
         for (p[2]=0;p[2]<=n;p[2]++)
           for (p[3]=0;p[3]<=n;p[3]++)
             for (p[4]=0;p[4]<=n;p[4]++)
               if ( (p[x1]                 v[p[1]][p[2]][p[3]][p[4]]=1;
     }
}

void work(){
     memset(F,0,sizeof(F));
     int p[5],c,i,delta;
     F[0][0][0][0]=1;
     for (c=1;c<=256;c++){
         for (delta=1;delta<=4;delta++)
           for (p[1]=0;p[1]<=n;p[1]++)
             for (p[2]=0;p[2]<=n;p[2]++)
               for (p[3]=0;p[3]<=n;p[3]++)
                 for (p[4]=0;p[4]<=n;p[4]++)
                   if (p[delta]){
                     int &t=F[p[1]][p[2]][p[3]][p[4]];
                     p[delta]–;
                     t    +=F[p[1]][p[2]][p[3]][p[4]];
                     p[delta]++;
                     if (t>=Mod) t-=Mod;
                   }
         for (p[1]=0;p[1]<=n;p[1]++)
           for (p[2]=0;p[2]<=n;p[2]++)
             for (p[3]=0;p[3]<=n;p[3]++)
               for (p[4]=0;p[4]<=n;p[4]++)
                 if (v[p[1]][p[2]][p[3]][p[4]])
                   F[p[1]][p[2]][p[3]][p[4]]=0;
     }
     printf("%05dn",F[n][n][n][n]);
}

int main(){
    int Tc,i;
    scanf("%d",&Tc);
    for (i=1;i<=Tc;i++){
        printf("Case %d: ",i);
        init();
        work();
    }
    return 0;
}