三角蛋糕(坐标规划类DP) 解题日志

三角蛋糕(trigon)

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

XP不想让蛋糕白白的被浪费，于是他把蛋糕分割成了一个个的小正三角形（如上图所示）。黑色的小正三角形表示老鼠把那一块咬坏了。XP想要切出一块最大的没被老鼠咬坏正三角形的蛋糕，可是最大的三角形有多大呢?

输入数据

第一行，一个整数N，表示XP把蛋糕纵向划分为N行。

接下来的N行，第i行包括了(n-i)*2+1个有效字符。“-”表示这块蛋糕是好的，“#”表示这块蛋糕被咬坏了。为了保持三角形的形状，输入文件中会出现空格。

输出数据

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

样例

输入:trigon.in

5

#-##----#

-----#-

---#-

-#-

-

输出:trigon.out

9

数据范围

对于30%的数据，满足n≤5

对于所有的测试数据，满足n≤100。

【思路剖析】

#include
using 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;
        }
    }
}