过了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;
}