40分求助
查看原帖
40分求助
474128
kiribati楼主2021/9/6 18:24

过了1 3 8 10四个点,找很久没找到问题...求大佬帮忙看看,万分感谢

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
using namespace std;

const int N = 16,M = 9,INF = 0x3f3f3f3f;
int n,m = 8;
int s[M][M];
int f[M][M][M][M][N];

int get(int x1,int y1,int x2,int y2)
{
	int ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
	return ans * ans;
}

int dp(int x1,int y1,int x2,int y2,int k)
{
	int& v = f[x1][y1][x2][y2][k];
	if(k == 1) return v = get(x1,y1,x2,y2);
	if(v >= 0) return v;
	
	v = INF;
	for(int i = x1 + 1;i < x2;i++)
	{
		v = min(v,dp(x1,y1,i,y2,k - 1) + get(i + 1,y1,x2,y2));
		v = min(v,dp(i + 1,y1,x2,y2,k - 1) + get(x1,y1,i,y2));
	}
	for(int j = y1 + 1;j < y2;j++)
	{
		v = min(v,dp(x1,y1,x2,j,k - 1) + get(x1,j + 1,x2,y2));
		v = min(v,dp(x1,j + 1,x2,y2,k - 1) + get(x1,y1,x2,j));
	}
	
	return v;
}

int main()
{
	cin >> n;
	for(int i = 1;i <= m;i++)
		for(int j = 1;j <= m;j++)
		{
			cin >> s[i][j];
			s[i][j]+= s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	memset(f,-0x3f,sizeof(f));
	
	printf("%d",dp(1,1,m,m,n));
	
	return 0;
}
2021/9/6 18:24
加载中...