三角蛋糕(trigon)
XP在机房里放了一块正三角形的大蛋糕,但是第二天他发现蛋糕被老鼠咬坏了。
XP不想让蛋糕白白的被浪费,于是他把蛋糕分割成了一个个的小正三角形(如上图所示)。黑色的小正三角形表示老鼠把那一块咬坏了。XP想要切出一块最大的没被老鼠咬坏正三角形的蛋糕,可是最大的三角形有多大呢?
输入数据
第一行,一个整数N,表示XP把蛋糕纵向划分为N行。
接下来的N行,第i行包括了(n-i)*2+1个有效字符。“-”表示这块蛋糕是好的,“#”表示这块蛋糕被咬坏了。为了保持三角形的形状,输入文件中会出现空格。
输出数据
一行一个整数,表示最大的三角形包括的小三角形数。
样例
输入:trigon.in
5
#-##----#
-----#-
---#-
-#-
-
输出:trigon.out
9
数据范围
对于30%的数据,满足n≤5
对于所有的测试数据,满足n≤100。
【思路剖析】
#includeusing namespace std; bool t[105][105]; int n; bool head[105][105];//确定朝上还是朝下,0下1上 int dp[105][105]; int main(){ cin>>n; for(int i=5;i>0;i--){ bool h=false; for(int j=1;j<=(n-i)*2+1;j++){ cin>> h=!h; } } }