洛谷P1436 棋盘分割题解

本题数据量比较小，建议使用记忆化搜索的方式来解决。

转移方程也比较简单，只需找到x1,y1到x2,y2当中的最小值即可。

这题主需要是训练二维前序和，原题是求方差，麻烦一些些。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 15, M = 9;
const int INF = 1e9;

int n, m = 8;
int s[M][M];
int w[M][M];
int f[M][M][M][M][N];
double X;
int get(int x,int y,int x1,int y1){
    int  sum=s[x1][y1]-s[x1][y-1]-s[x-1][y1]+s[x-1][y-1];
    return  sum*sum;
}

int dp(int x,int y,int x1,int y1 ,int cnt){
    int i,j;
    int & v =f[x][y][x1][y1][cnt];
    if(v>=0)
    return v;
    if(cnt==1){
    v=get(x,y,x1,y1);
    return v;
    }

    v=INF;
    for(i=x;i<x1;i++){
        v=min(v,get(x,y,i,y1)+dp(i+1,y,x1,y1,cnt-1));
        v=min(v,get(i+1,y,x1,y1)+dp(x,y,i,y1,cnt-1));
    }
    for(i=y;i<y1;i++){
        v=min(v,get(x,y,x1,i)+dp(x,i+1,x1,y1,cnt-1));
        v=min(v,get(x,i+1,x1,y1)+dp(x,y,x1,i,cnt-1));
    }
    return v;
}
int main(){
    cin >> n;
    int i,j;
    for(i=1;i<=8;i++){
        for(j=1;j<=8;j++)
        cin>>w[i][j];
    }
    for(i=1;i<=8;i++){
        for(j=1;j<=8;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+w[i][j];
        }
    }
    memset(f, -1, sizeof f);
    cout<<dp(1, 1, 8, 8, n)<<endl;


    return 0;
}

View Code