Codeforces 372B Counting Rectangles is Fun：dp套dp

题目链接：http://codeforces.com/problemset/problem/372/B

题意：

　　给你一个n*m的01矩阵(1 <= n,m <= 40)。

　　然后有t组询问(a,b,c,d)，问你：

　　　　在以(a,b)为左上角，以(c,d)为左下角，围成的矩形范围中，有多少全是0的矩形。

题解：

　　这题是dp套dp……

　　首先解决dp1：

　　　　表示状态：

　　　　　　f[a][b][c][d] = Rectangles number

　　　　　　表示左上角为(a,b)，右下角的范围在(c,d)以内的全0矩形的个数。

　　　　如何转移：

　　　　　　f[a][b][c][d] = f[a][b][c-1][d] + f[a][b][c][d-1] - f[a][b][c-1][d-1] + check(a,b,c,d)

　　　　　　简单的容斥原理。

　　　　　　其中，如果左上角为(a,b)，右下角为(c,d)的矩形中全是0，则check(a,b,c,d)为1，否则为0（要用到二维前缀和）。

　　　　边界条件：

　　　　　　set f = 0

　　　　复杂度O(N^4)。

　　然后解决dp2：

　　　　表示状态：

　　　　　　dp[a][b][c][d] = Rectangles number

　　　　　　表示在(a,b)和(c,d)围成的范围内的全0矩形个数。

　　　　　　显然有：

　　　　　　　　dp[a][b][c][d] = ∑ f[i][j][c][d] (a<=i<=c, b<=j<=d)

　　　　如何转移：

　　　　　　dp[a][b][c][d] = dp[a+1][b][c][d] + dp[a][b+1][c][d] - dp[a+1][b+1][c][d] + f[a][b][c][d]

　　　　　　还是根据容斥原理，不过在这里a,b,c,d要倒着枚举。

　　　　边界条件：

　　　　　　set dp = 0

　　　　复杂度O(N^4)。

　　所以对于每一次询问，直接输出dp[a][b][c][d]即可。

　　总复杂度O(N^4 + t)

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 45

 using namespace std;

 int n,m,t;

 int v[MAX_N][MAX_N];

 int s[MAX_N][MAX_N];

 int f[MAX_N][MAX_N][MAX_N][MAX_N];

 int dp[MAX_N][MAX_N][MAX_N][MAX_N];

 void read()

 {

     cin>>n>>m>>t;

     char c;

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

     {

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

         {

             cin>>c;

             v[i][j]=c-'';

         }

     }

 }

 void cal_s()

 {

     memset(s,,sizeof(s));

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

     {

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

         {

             s[i][j]=s[i][j-]+s[i-][j]-s[i-][j-]+v[i][j];

         }

     }

 }

 int check(int a,int b,int c,int d)

 {

     int sum=s[c][d]-s[c][b-]-s[a-][d]+s[a-][b-];

     return sum== ?  : ;

 }

 void cal_f()

 {

     memset(f,,sizeof(f));

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

     {

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

         {

             for(int c=a;c<=n;c++)

             {

                 for(int d=b;d<=m;d++)

                 {

                     f[a][b][c][d]=f[a][b][c-][d]+

                         f[a][b][c][d-]-

                         f[a][b][c-][d-]+

                         check(a,b,c,d);

                 }

             }

         }

     }

 }

 void cal_dp()

 {

     memset(dp,,sizeof(dp));

     for(int a=n;a>=;a--)

     {

         for(int b=m;b>=;b--)

         {

             for(int c=n;c>=a;c--)

             {

                 for(int d=m;d>=b;d--)

                 {

                     dp[a][b][c][d]=dp[a+][b][c][d]+

                         dp[a][b+][c][d]-

                         dp[a+][b+][c][d]+

                         f[a][b][c][d];

                 }

             }

         }

     }

 }

 void work()

 {

     cal_s();

     cal_f();

     cal_dp();

     int a,b,c,d;

     while(t--)

     {

         cin>>a>>b>>c>>d;

         cout<<dp[a][b][c][d]<<endl;

     }

 }

 int main()

 {

     read();

     work();

 }

巴特西

Codeforces 372B Counting Rectangles is Fun：dp套dp

最新文章

热门文章