5维dp永远滴神

#include<bits/stdc++.h>
using namespace std;
int n,s[10][10],dp[10][10][10][10][20];//dp[a][b][c][d][e]表示左上角为(a,b)右下角为(c,d)的矩形切n刀的最小数值 
int main(){
	cin>>n;
	for(int i=1;i<=8;i++){
		for(int j=1;j<=8;j++){
			cin>>s[i][j];
		}
	}
	memset(dp,0x3f,sizeof dp);
	for(int a=1;a<=8;a++){
		for(int b=1;b<=8;b++){
			for(int c=a;c<=8;c++){
				for(int d=b;d<=8;d++){
					dp[a][b][c][d][0]=0;
					for(int i=a;i<=c;i++){
						for(int j=b;j<=d;j++){
							dp[a][b][c][d][0]+=s[i][j];
						}
					}
					dp[a][b][c][d][0]*=dp[a][b][c][d][0];
					//cout<<dp[a][b][c][d][0]<<endl;
				}
			}
		}
	}
	for(int k=1;k<n;k++){//枚举刀数 
		for(int a=1;a<=8;a++){//枚举区间 
			for(int b=1;b<=8;b++){
				for(int c=a;c<=8;c++){//枚举区间 
					for(int d=b;d<=8;d++){
						for(int i=b;i<d;i++){//竖着切 
							dp[a][b][c][d][k]=min(dp[a][b][c][d][k],dp[a][b][c][i][k-1]+dp[a][i+1][c][d][0]);
							dp[a][b][c][d][k]=min(dp[a][b][c][d][k],dp[a][b][c][i][0]+dp[a][i+1][c][d][k-1]);
						}
						for(int j=a;j<c;j++){//横着切 
							dp[a][b][c][d][k]=min(dp[a][b][c][d][k],dp[a][b][j][d][k-1]+dp[j+1][b][c][d][0]);
							dp[a][b][c][d][k]=min(dp[a][b][c][d][k],dp[a][b][j][d][0]+dp[j+1][b][c][d][k-1]);
						}
					}
				}
			}
		}
	}
	cout<<dp[1][1][8][8][n-1];
	return 0;
}