BZOJ1126: [POI2008]Uci

$n \leq 100,m \leq 100$，$n*m$的01矩形，问从左下角开始往上走，每次转弯只能向右，不能经过重复点，不能撞到1，到达点$(x,y)$的方案数，$mod \ \ k$。

感人肺腑的细节题写了一天。。

可以发现他在做一个绕圈运动，运动的过程中逐渐限制自己的活动范围，因此可以用活动范围和射入方向表示状态（这样也就确定了它的位置），$f[L][R][U][D][0123]$--沿左边向上、沿上边向右、沿右边向下、沿下边向左射入矩形$[L,R,U,D]$的方案。如图：

这样转移可以用一个前缀和转移。比如上转右的：

用纵方向一个前缀的蓝色矩形转移到右方向的一个矩形。这样就可以$O(1)$转移了。

由于四维开不下，要把L那一维滚动掉，所以记前缀和的时候，左转上那个数组不要清，那里实际保留了所有$L_2<L$转移到$L$的状态的前缀和。

记答案的时候，在目标处转弯时记录答案。注意最后一圈不要记重了。这句话是啥意思我也说不清，看代码吧QAQ

 //#include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 //#include<time.h>

 //#include<complex>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 int n,m,mod,tx,ty;

 #define maxn 111

 int f[][maxn][maxn][maxn][],cur,sum[maxn][maxn][maxn][],bl[maxn][maxn][]; char s[maxn];

 bool mp[maxn][maxn]; //0 up 1 right 2 down 3 left

 int main()

 {

     scanf("%d%d%d%d%d",&n,&m,&mod,&ty,&tx);

     for (int i=;i<=n;i++)

     {

         scanf("%s",s+);

         for (int j=;j<=m;j++) mp[i][j]=(s[j]=='+');

     }

     for (int j=;j<=m;j++)

     {

         bl[][j][]=;

         for (int i=;i<=n;i++) if (mp[i][j]) bl[i][j][]=bl[i-][j][];

         else bl[i][j][]=i;

     }

     for (int i=;i<=n;i++)

     {

         bl[i][m+][]=m+;

         for (int j=m;j;j--) if (mp[i][j]) bl[i][j][]=bl[i][j+][];

         else bl[i][j][]=j;

     }

     for (int j=;j<=m;j++)

     {

         bl[n+][j][]=n+;

         for (int i=n;i;i--) if (mp[i][j]) bl[i][j][]=bl[i+][j][];

         else bl[i][j][]=i;

     }

     for (int i=;i<=n;i++)

     {

         bl[i][][]=;

         for (int j=;j<=m;j++) if (mp[i][j]) bl[i][j][]=bl[i][j-][];

         else bl[i][j][]=j;

     }

     cur=; for (int i=;i<=n;i++) sum[m][i][n][]=;

     int ans=;

     for (int L=;L<=ty+;L++)

     {

         cur^=;

         for (int R=m;R>=ty;R--) for (int U=;U<=tx;U++) for (int D=max(U,tx);D<=n;D++)

         {

             sum[R][U][D][]=sum[R+][U][D][];

             f[cur][R][U][D][]=;

             if (bl[D][L-][]<U)

             {

                 f[cur][R][U][D][]=sum[R][U][D][];

                 sum[R][U][D][]+=f[cur][R][U][D][]; sum[R][U][D][]-=sum[R][U][D][]>=mod?mod:;

             }

             if (L-==ty && U==tx) ans+=f[cur][R][U][D][],ans-=ans>=mod?mod:;

         }

         if (L==ty+) break;

         for (int D=n;D>=tx;D--) for (int R=ty;R<=m;R++) for (int U=;U<=tx+;U++)

         {

             sum[R][U][D][]=sum[R][U][D+][];

             f[cur][R][U][D][]=;

             if (bl[U-][L-][]>R)

             {

                 f[cur][R][U][D][]=sum[R][U-][D][];

                 sum[R][U][D][]+=f[cur][R][U][D][]; sum[R][U][D][]-=sum[R][U][D][]>=mod?mod:;

             }

             if (U-==tx && R==ty) ans+=f[cur][R][U][D][],ans-=ans>=mod?mod:;

         }

         for (int D=n;D>=tx;D--) for (int R=ty;R<=m;R++) sum[R][][D][]=sum[R][][D+][];

         for (int U=;U<=tx;U++) for (int D=max(tx,U);D<=n;D++) for (int R=ty-;R<m;R++)

         {

             f[cur][R][U][D][]=;

             if (bl[U][R+][]>D)

             {

                 f[cur][R][U][D][]=sum[R+][U][D][];

                 sum[R][U][D][]+=f[cur][R][U][D][]; sum[R][U][D][]-=sum[R][U][D][]>=mod?mod:;

             }

             if (D==tx && R+==ty) ans+=f[cur][R][U][D][],ans-=ans>=mod?mod:;

         }

         for (int U=;U<=tx;U++) for (int D=tx-;D<=n;D++) for (int R=ty;R<=m;R++)

         {

             if (U) sum[R][U][D][]=sum[R][U-][D][];

             f[cur][R][U][D][]=;

             if (bl[D+][R][]<L)

             {

                 f[cur][R][U][D][]=sum[R][U][D+][];

                 sum[R][U][D][]+=f[cur][R][U][D][]; sum[R][U][D][]-=sum[R][U][D][]>=mod?mod:;

             }

             if (D+==tx && L==ty) ans+=f[cur][R][U][D][],ans-=ans>=mod?mod:;

         }

         for (int U=;U<=tx;U++) for (int R=ty;R<=m;R++) sum[R][U][n][]=sum[R][U-][n][];

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

BZOJ1126: [POI2008]Uci

最新文章

热门文章