三角蛋糕(坐标规划类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;
        }
    }
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注