60分求助
查看原帖
60分求助
428449
Amon_Xolotl楼主2023/8/28 18:32
#include<bits/stdc++.h>
using namespace std;
const int N=103;
int n,m,dp[N][3][N][3][13],k;
int a[N][3],sum[N][3],num[N][3],ans=0;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			scanf("%d",&a[i][j]);
			sum[i][j]=sum[i][j-1]+a[i][j];
			num[i][j]=num[i-1][j]+sum[i][j];
		}
	}
//	for(int i=1;i<=n;++i)
//	{
//		for(int j=1;j<=m;++j)
//		{
//			cout<<num[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	memset(dp,-0x3f,sizeof(dp));
	for(int x1=1;x1<=n;++x1)
	{
		for(int y1=1;y1<=m;++y1)
		{
			for(int x2=x1;x2<=n;++x2)
			{
				for(int y2=y1;y2<=m;++y2)
				{
					dp[x1][y1][x2][y2][0]=0;
				}
		    }
		}
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			dp[1][1][i][j][1]=num[i][j];
		}
	}
	for(int s=1;s<=k;++s)
	{
		for(int x1=1;x1<=n;++x1)
		{
			for(int y1=1;y1<=m;++y1)
			{
				for(int x2=x1;x2<=n;++x2)
				{
					for(int y2=y1;y2<=m;++y2)
					{
						for(int x3=1;x3<=x2;++x3)
						{
							for(int y3=1;y3<y1;++y3)
							{
								for(int x4=x3;x4<=x2;++x4)
								{
									for(int y4=y3;y4<y1;++y4)
									{
										dp[x1][y1][x2][y2][s]=max(dp[x1][y1][x2][y2][s],dp[x3][y3][x4][y4][s-1]+num[x2][y2]-num[x1-1][y2]-num[x2][y1-1]+num[x1-1][y1-1]);
								//		if(dp[x3][y3][x4][y4][s-1]+num[x2][y2]-num[x1-1][y2]-num[x2][y1-1]+num[x1-1][y1-1]==8)
								//		{
								//			cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<x3<<" "<<y3<<" "<<x4<<" "<<y4<<endl;
								//		}
									}
								}
							}
						}
						for(int x3=1;x3<x1;++x3)
						{
							for(int y3=1;y3<=y2;++y3)
							{
								for(int x4=x3;x4<x1;++x4)
								{
									for(int y4=y3;y4<=y2;++y4)
									{
										dp[x1][y1][x2][y2][s]=max(dp[x1][y1][x2][y2][s],dp[x3][y3][x4][y4][s-1]+num[x2][y2]-num[x1-1][y2]-num[x2][y1-1]+num[x1-1][y1-1]);
									//	if(dp[x3][y3][x4][y4][s-1]+num[x2][y2]-num[x1-1][y2]-num[x2][y1-1]+num[x1-1][y1-1]==8)
									//	{
									//		cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<x3<<" "<<y3<<" "<<x4<<" "<<y4<<endl;
									//	}
									}
								}
							}
						}
						if(s==k)
						{
							ans=max(ans,dp[x1][y1][x2][y2][s]);
						//	if(dp[x1][y1][x2][y2][s]==8)
						//	{
						//		cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
						//	}
						}
					}
				}
			}
		}
	}
	//cout<<dp[1][1][2][1][1]<<endl;
	cout<<ans;
	return 0;
}
2023/8/28 18:32
加载中...