【动态规划】P1548 棋盘问题

· · 个人记录

P1548 棋盘问题

本例数据范围较小，有直观简单的O(nnmm)朴素算法，这里不表。

一、动态规划 时间：O(nm)，空间:O(nm)

1、正方形

本格构成的正方形=之前形成的正方形数+本格形成的正方数

之前形成的正方形为：左边格+上边格-左上格（重复）

本格形成的正方形为（必须包含本格）：共有min(i,j)个。

递堆方程：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+min(i,j);

2、长方形

同上，只是本格到底形成多个长方形？不好算，我们算本格形成多少个矩形（包含正、长方形），共有i*j个，减去正方形个数，得到长方形个数

递堆方程：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+i*j-min(i,j);

#include <bits/stdc++.h>
using namespace std;

int f[105][105],g[105][105];
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+min(i,j);
            g[i][j]=g[i-1][j]+g[i][j-1]-g[i-1][j-1]+i*j-min(i,j);
        }
    }
    cout<<f[n][m]<<" "<<g[n][m];
    return 0;
}

二、递推1，时间：O(nm)，空间：O(1)

设一个n*m的矩形：

必须包含[n][m]格的矩形有n*m个，正方形有min(n,m)个

必须包含[n][m-1]格的矩形有n*(m-1)个，正方形有min(n,m-1)个

必须包含[n][m-2]格的矩形有n*(m-2)个，正方形有min(n,m-2)个

必须包含[n-1][m]格的矩形有(n-1)*m个，正方形有min(n-1,m)个

必须包含[n-1][m-1]格的矩形有(n-1)*(m-1)个，正方形有min(n-1,m-1)个

必须包含[n-1][m-2]格的矩形有(n-1)*(m-2)个，正方形有min(n-1,m-2)个

#include <bits/stdc++.h>
using namespace std;

int main() {
    int s1=0,s2=0;
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            s1+=(n-i+1)*(m-j+1);
            s2+=min(i,j);
        }
    }
    cout<<s2<<" "<<s1-s2;
    return 0;
}

三、递推2，时间：O(min(n,m))，空间：O(1)

1、矩形：

必须包含[n][m]格的矩形有n*m个

必须包含[n][m-1]格的矩形有n*(m-1)个

必须包含[n][m-2]格的矩形有n*(m-2)个

那么第[n]行的矩形共n*m+n*(m-1)+n*(m-2)...个，即nm(m+1)/2个。

同理第[n-1]行的矩形共(n-1)m(m+1)/2个。

同理第[n-2]行的矩形共(n-2)m(m+1)/2个。

那么n*m的矩形共包含nm(m+1)/2+(n-1)m(m+1)/2+(n-2)m(m+1)/2... 即：n(n+1)/2*m(m+1)/2个。

2、正方形

一个n*m的矩形：

包含边长为1的正方形有：n*m个

包含边长为2的正方形有：(n-1)*(m-1)个

...

#include <bits/stdc++.h>
using namespace std;

int main() {
    int s1,s2=0;
    int n,m;
    cin>>n>>m;
    s1=n*(n+1)*m*(m+1)/4;
    while(n&&m){
        s2+=n*m;
        n--;m--;
    }
    cout<<s2<<" "<<s1-s2;
    return 0;
}

四、递推3，时间：O(1)，空间：O(1)

接递推2，我们再进一步推正方形：

正方形个数为：n*m+(n-1)*(m-1)+(n-2)*(m-2)..

括号开出来：n*m+n*m-(n+m)+1+n*m-2(n+m)+4+....

共有min(n,m)+1项，我们设t=min(n,m)。

1、共有t+1个n*m：(t+1)*n*m

2、共有-0(n+m)-1(n+m)-2(n+m)...-t(n+m)，得t*(t+1)/2*(n+m)

3、 1+4+9+16....t个平方差相加得t(t+1)(2t+1)/6

最后的公式：m*n*(t+1)+t*(t+1)*(2*t+1)/6-(m+n)*t*(t+1)/2

#include <bits/stdc++.h>
using namespace std;

int main() {
    int s1,s2=0,t;
    int n,m;
    cin>>n>>m;
    s1=n*(n+1)*m*(m+1)/4;
    t=min(n,m);
    s2=m*n*(t+1)+t*(t+1)*(2*t+1)/6-(m+n)*t*(t+1)/2;
    cout<<s2<<" "<<s1-s2;
    return 0;
}