坐标dp-三角蛋糕
  • 板块学术版
  • 楼主Are_You_Ready
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/24 20:07
  • 上次更新2023/11/3 01:26:14
查看原帖
坐标dp-三角蛋糕
513923
Are_You_Ready楼主2023/8/24 20:07

三角蛋糕 Description XP在机房里放了一块正三角形的大蛋糕,但是第二天他发现蛋糕被老鼠咬坏了。

XP不想让蛋糕白白的被浪费,于是他把蛋糕分割成了一个个的小正三角形(具体的图可以去CSDN上搜,贴不过来)。 黑色的小正三角形表示老鼠把那一块咬坏了。 XP想要切出一块最大的没被老鼠咬坏正三角形的蛋糕,可是最大的三角形有多大呢?

Input 第一行,一个整数 NN,表示XP把蛋糕纵向划分为 NN 行。 接下来的 NN 行,第 ii 行包括了 (n−i)∗2+1(n−i)∗2+1 个有效字符。 “-”表示这块蛋糕是好的,“#”表示这块蛋糕被咬坏了。 为了保持三角形的形状,输入文件中会出现空格。

Output 一行一个整数,表示最大的三角形包括的小三角形数。

#include<bits/stdc++.h>
using namespace std;
string a[10001]={"99999"};
int dp[1001][1001],f[1001][1001];
int main()
{
	int n,maxn=0,maxn1=0;
	cin>>n;
	memset(dp,0,sizeof(dp));
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]; 
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=(n-i)*2;j++)
		{
			if(a[i][j]=='0')
			dp[i][j]=min(dp[i-1][j],dp[i-1][j+1])+1,maxn=max(dp[i][j],maxn);
		}
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=0;j<=(n-i)*2;j++)
		{
			if(a[i][j]=='0')
			f[i][j]=min(f[i+1][j],f[i+1][j+1])+1,maxn1=max(f[i][j],maxn1);
		}
	}
	cout<<max(maxn*maxn,maxn1*maxn1);
}

哪里错了呀

2023/8/24 20:07
加载中...