标签：dfs+剪枝。

题解：

　　这道题看着就像一道dfs题目，没有什么算法可以用来算这个东西，于是想想暴搜。
　　如果我们确定因为是2*2的子矩阵的和，如果确定了其中三个，那么就可以确定第四个，发现如果确定了第一行和第一列的话，就可以确定整个矩阵了，于是我们枚举只有399个了。
　　因为要求字典序最小，我们先默认第一行和第一列全部是0，求出一个矩阵。我们先搜索第一行，从左到右。发现在（1,1）位置的数+k，那么在除了第一行和第一列的矩阵中，要合法，就要i+j为偶数的-=k，i+j为奇数的+=k即可。同样在（1，j）位置+=k，那么只影响这一列，便偶数行号-=k，奇数行号+=k即可。我们在保证了第一行最小的情况下，只要保证第一列最小即可满足字典序最小，因为确定第一行和第一列可以唯一的确定一个矩阵。
　　第一行我们暴搜，当然需要剪枝了，对于每搜到第一行的一个数，就要扫一遍这一列，并且更新这一列的每个元素的所在行的行首的范围，也就是矩阵第一列每一个元素的范围，因为矩阵中的每一个元素只被三个数影响，那就是（1,1），以及行首与列首。更新了第一列每一个元素的范围之后，如果冲突即（L>R）那么就返回0。
　　这里有一个技巧：按道理范围只要开一个O(n)的数组即可，但是这样需要备份，因为如过搜索失败了，那么回溯也要恢复范围数组的值，很麻烦，那么我们直接开一个二维数组，每次更新时取上一列的值与当前值比较之后再更新，这样就没有回溯的问题了，因为我们是从左到右枚举第一行的。

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int MAXN=,INF=0x3f3f3f3f;

 int n,m,P;

 int L[MAXN][MAXN],R[MAXN][MAXN],A[MAXN][MAXN];

 inline int gi(){int res; scanf("%d",&res); return res;}

 int F(int x){return (x&)?:-;}

 int cal(int x,int y) { return A[x][y]+F(x+y)*A[][]+F(y)*L[x][m]+F(x)*A[][y]; }

 bool dfs(int y)

 {

   if(y>m)return ;

   int bacl[MAXN]={},bacr[MAXN]={};

   for(A[][y]=;A[][y]<P;A[][y]++)

     {

       bool flag=;

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

         {

           int tl=(A[i][y] + A[][]*F(i+y) + A[][y]*F(i)) * F(y+);

           int tr=(A[i][y] + A[][]*F(i+y) + A[][y]*F(i)-(P-)) * F(y+);

           if(tl>tr)swap(tl,tr);

           L[i][y]=max(L[i][y-],tl);

           R[i][y]=min(R[i][y-],tr);

           if(L[i][y]>R[i][y])

             {flag=; break;}

         }

       if(flag)

         if(dfs(y+))

           return ;

     }

   return ;

 }

 int main()

 {

   n=gi(); m=gi(); P=gi();

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

     {

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

         {

           A[i][j]=gi();

           if(i!= && j!=)

             A[i][j]-=(A[i][j-]+A[i-][j]+A[i-][j-]);

           R[i][j]=P-;

         }

     }

   for(;A[][]<P;A[][]++)

     {

       if(dfs())

         {

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

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

               {

                 if(j== && i>)

                   printf("%d ",L[i][m]);

                 else if(i== && j>)

                   printf("%d%c",A[][j],j==m?'\n':' ');

                 else

                   printf("%d%c",cal(i,j),j==m?'\n':' ');

               }

           return ;

         }

     }

   return ;

 }

巴特西

[HNOI2010] 矩阵 matrix

题解：

最新文章

热门文章