321. Chessboard segmentation (2D interval DP)

 321. Chessboard division - AcWing Question bank

The question ：

• A matrix can be crosscut , Or side cutting , As shown in the figure
• For a chessboard cut into two parts , You can and can only select one to continue cutting down

Find the minimum variance , Due to mean square deviation X Fix ,n Fix , What we need to calculate is the area of the divided sub rectangle (xi-X)*(xi-X).

therefore , You can use the search method , Keep raising the minimum

analysis ： Two dimensional interval dp, In fact, it is similar to the digital triangle model , Because segmentation may not have a linear recursive relationship , So we use the method of memory search .

• Crosscut i, In two parts [(x1,y1)~(i,y2)],[(i+1,y2)~(x2,y2)]
• Vertical cutting i, In two parts [(x1,y1)~(x2,i)],[(x2,i+1)~(x2,y2)]

initialization ： All initialized to infinity , Due to the particularity of planned search , So first initialize to a negative number , Enter to reinitialize

State transition equation / State calculation ：

According to the position of cross cutting and vertical cutting i Different , And which subset to continue to divide after division , It can be divided into multiple sets

Crosscut , It is divided into two subsets , Both subsets can be further divided , Another direct calculation

• dp[x1][y1][x2][y2][k]=max(dp[x1][i][x2][y2][k]+sum[x1~i][y1~y2]);
• dp[x1][y1][x2][y2][k]=max(dp[x1][y1][i+1][y2][k]+sum[i+1~]

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=16;
const int inf=1e9;
int s[N][N];
double dp[N][N][N][N][N];
double X;
double get(int x1,int y1,int x2,int y2)
{
    int a=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
    return (a-X)*(a-X);
}
double dfs(int x1,int y1,int x2,int y2,int k)
{
    double &v=dp[x1][y1][x2][y2][k];// For simplicity , add v
    if(v>=0) return v;
    if(k==1) return get(x1,y1,x2,y2);
    v=1e9;  // For the minimum , Initialize to infinity 
    
    for(int i=x1;i<x2;i++)
    {// Crosscutting subset 
        v=min(v,dfs(i+1,y1,x2,y2,k-1)+get(x1,y1,i,y2));
        v=min(v,dfs(x1,y1,i,y2,k-1)+get(i+1,y1,x2,y2));
    }
    
    for(int i=y1;i<y2;i++)
    {// Vertically cut subset 
        v=min(v,dfs(x1,i+1,x2,y2,k-1)+get(x1,y1,x2,i));
        v=min(v,dfs(x1,y1,x2,i,k-1)+get(x1,i+1,x2,y2));
    }
    return v;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
            cin>>s[i][j];
    for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
            s[i][j]+=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
    
    X=(double)s[8][8]/n;
    memset(dp,-1,sizeof dp);    // Because the integral may be 0, So take -1
    double a=dfs(1,1,8,8,n)/n;
    printf("%.3lf",sqrt(a));
    return 0;    
}