[POJ] 1191 [LUOGU] P1436 棋盘分割

那个均方差，可以通过展开、合并Σ，发现最终只有Xi^2会对答案造成影响，其他都是定值，所以求出最小的和的平方就行。

其实这才是这题最难的部分，以下都是码农部分。

f[x1][y1][x2][y2][k] 从(x1,y1)到(x2,y2)这个矩形，割k次的最小平方和。

边界 k==1时，就是矩形本身面积的平方和。

其余情况，分两种，横着割和竖着割，一块继续割，另一块的面积平方加入答案。

（强烈建议纸笔画图标出坐标，不用纠结下标+1/-1问题）

维数比较多，所以用了记忆化，好写一点。

洛谷AC代码

//Stay foolish,stay hungry,stay young,stay simple

#include<iostream>

using namespace std;

int n;

int a[9][9],s[9][9];

int f[9][9][9][9][16];

inline int S(int x1,int y1,int x2,int y2){

    x1--;y1--;//it includes (x1,y1) ,so..

    return s[x2][y2]-s[x2][y1]-s[x1][y2]+s[x1][y1];

}

int slove(int x1,int y1,int x2,int y2,int k){

    int &ans=f[x1][y1][x2][y2][k];

    if(k==1) return S(x1,y1,x2,y2)*S(x1,y1,x2,y2);//actually there is no need to calc it twice

    if(ans) return ans;

    ans=1<<30;//big enough!

    if(x1<x2)

    for(int i=x1;i<x2;i++){

        int t1=slove(x1,y1,i,y2,k-1);

        int s1=S(i+1,y1,x2,y2);

        int t2=slove(i+1,y1,x2,y2,k-1);

        int s2=S(x1,y1,i,y2);

        ans=min(ans,min(t1+s1*s1,t2+s2*s2));

    }

    if(y1<y2)//maybe useful?

    for(int i=y1;i<y2;i++){

        int t1=slove(x1,y1,x2,i,k-1);

        int s1=S(x1,i+1,x2,y2);

        int t2=slove(x1,i+1,x2,y2,k-1);

        int s2=S(x1,y1,x2,i);

        ans=min(ans,min(t1+s1*s1,t2+s2*s2));

    }

    return ans;

}

int main(){

    cin>>n;

    for(int i=1;i<=8;i++)

        for(int j=1;j<=8;j++)

            cin>>a[i][j];

    for(int i=1;i<=8;i++)

        for(int j=1;j<=8;j++)

            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

    cout<<slove(1,1,8,8,n);

    return 0;

}

巴特西

[POJ] 1191 [LUOGU] P1436 棋盘分割

最新文章

热门文章