http://acm.zju.edu.cn/show_problem.php?pid=1245

典型的DP，题目不难，锻炼一下DP思维。

分析：

题目要求是在一个三角点阵中（有黑点和白点）找到最大的白三角点阵。

题目提示百三角点阵可能是朝上的。

很显然题目有最优子结构：

       定义f[i][j]表示以点(i,j)为三角形顶点的最大百三角点阵包含点的个数。

则：

f[0][j] = 1，当triangle[0][1] == ‘-’；

f[0][j] = 0，当triangle[0][1] == ‘#’；

f[i][j] = 1，当triangle[i-1][j+1] == ’#’ && triangle[i][j] == ‘-’ && i > 0；

f[i][j] = min(f[i-1][j] , f[i-1][j+2]) - ∩(f[i-1][j] , f[i-1][j+2])，当triangle[i-1][j+1] == ’-’ && triangle[i][j] == ‘-’ && i > 0；

f[i][j] = 0，当 triangle[i][j] == ‘#’ && i > 0；

这是顶点超下的三角统计方式。

f[n-1][1] = 1，当triangle[n-1][1] == '-'；

f[n-1][1] = 0，当triangle[n-1][1] == '#'；

f[i][j] = 1，当triangle[i+1][j-1] == ’#’ && triangle[i][j] == ‘-’ && i >= 0 && i < n-1；

f[i][j] = min(f[i+1][j] , f[i+1][j-2]) - ∩(f[i+1][j] , f[i+1][j-2])，当triangle[i+1][j-1] == ’-’ && triangle[i][j] == ‘-’ && i > 0 && i < n-1；

f[i][j] = 0，当 triangle[i][j] == ‘#’ && i >= 0 && i < n-1；

这是顶点朝上的三角统计方式。

有了以上公式，code is easy！