自动搬运

查看原文

来自洛谷，原作者为

	Arcturus1350 **

搬运于2025-08-24 21:25:04，当前版本为作者最后更新于2018-02-22 11:26:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实呢大致思路和下面的大佬们都很像。 发这篇题解的目的就是加了一点优化骗分技巧。

转移方程：

设$dp[i][j][x][y][k]$表示左上$(i,j)$，右下$(x,y)$，第$k$次割的最大面积。 则对于

$\sum_{k=1}^{n}$

开始更新，有：(一口气读完这个方程)

$∑_{i=1}^{8}∑_{j=1}^{8}∑_{x=1}^{8}∑_{y=1}^{8}$

$a=j……y-1;b=i……x-1;$

$dp[i][j][x][y][k]=$

$min($

$min(dp[i][j][x][a][k-1]+dp[i][a+1][x][y][0],dp[i][j][x][a][0]+dp[i][a+1][x][y][k-1]),$

$min(dp[i][j][b][y][k-1]+dp[b+1][j][x][y][0],dp[i][j][b][y][0]+dp[b+1][j][x][y][k-1])$

$);$

但是。

别以为推出了方程就万事大吉了！！！

您的边界条件呢（这题很简单）。 但是这题的初始化是重点！！！重点！！！重点！！！ 好几篇都是6重循环暴力算的。 本宝宝：前缀和先求出来就好了。

那么好，初始化的话是要把所有左上为$(i,j)$右上为$(x,y)$,割了0次的面积求出来。这里，本宝宝用了一个前缀和的思想和容斥原理。 先在输入的时候就处理出来所有左上$(1,1)$右上$(i,j)$的得分（前缀和）； 然后利用容斥原理（具体见代码） 能少些三两个循环呢。。。 上代码（码风不好请原谅）

//by Su Qingnian
//QAQ
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;//n是总共切的刀数
int map[9][9];//存图，价值
int sum[9][9];//前缀和数组
int dp[9][9][9][9][15];//dp暴力数组
inline void add(int i,int j)
{
//这个函数是计算前缀和数组。左上(1,1)右下(i,j)的价值
//好好想想为什么。（扩展这个点时左边矩形+右边矩形-重叠的部分+这个点的价值）
    sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+map[i][j];
    return ;
}
inline int s(int x1,int y1,int x2,int y2)
{
//这个是用来计算左上(x1,y1)右下(x2,y2)的价值
//还是容斥原理
    int now=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
    return now;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=8;i++)
      for(int j=1;j<=8;j++)
      scanf("%d",&map[i][j]),
      add(i,j);//输入，处理前缀和
    
//debug
//	for(int i=1;i<=8;i++,puts(""))
//	  for(int j=1;j<=8;j++)
//	  printf("%-5d ",sum[i][j]); 
//处理切0刀时各矩形价值的平方
    for(int i=1;i<=8;i++)
     for(int j=1;j<=8;j++)
       for(int x=i;x<=8;x++)
         for(int y=j;y<=8;y++)
           dp[i][j][x][y][0]+=s(i,j,x,y),
           dp[i][j][x][y][0]*=dp[i][j][x][y][0];
//dp过程，深吸一口气读完这一面方程。
	for(int k=1;k<n;k++)
      for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
          for(int x=i;x<=8;x++)
            for(int y=j;y<=8;y++)
            {
            	int minn=0x3f3f3f3f;
            	for(int a=j;a<y;a++)
                  minn=min(minn,min(dp[i][j][x][a][k-1]+dp[i][a+1][x][y][0],dp[i][j][x][a][0]+dp[i][a+1][x][y][k-1]));
                for(int b=i;b<x;b++)
                  minn=min(minn,min(dp[i][j][b][y][k-1]+dp[b+1][j][x][y][0],dp[i][j][b][y][0]+dp[b+1][j][x][y][k-1]));
            	dp[i][j][x][y][k]=minn;
            }
    printf("%d",dp[1][1][8][8][n-1]); 
 //输出，程序拜拜。
    return 0;
}