题解：P4813 [CCO 2014] Troy 与三角形

· · 题解

题解：P4813 [CCO 2014] Troy 与三角形

题目传送门

虽是一道绿题，但码量只有一道橙题。
题目让求#号三角形的数量，考虑 dp，其中 dp_{i,j} 表示第 i 行第 j 列为右下角出现#号三角形的个数。
很显然，每一个点的#号三角形的个数其实是和它在右下角最大形成的#号三角形高度相等。而每个点在右下角最大形成的#号三角形高度只收到如图中两个因素的影响：

显然 dp_{i,j}=\min(x,\dfrac{y+1}{2})，而 x=dp_{i-1,j-1}+1。所以 dp_{i,j}=\min(dp_{i-1,j-1}+1,\dfrac{y+1}{2})。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
char c[2005][2005];int cnt,ans,n,dp[2005][2005];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>c[i][j];//输入
    for(int i=1;i<=n;i++){
        cnt=0;for(int j=1;j<=n;j++){
            if(c[i][j]=='#'){
                cnt++;//cnt对应题目中的y
dp[i][j]=min(dp[i-1][j-1]+1,(cnt+1)/2);//dp转移
                ans+=dp[i][j];
            }
            else cnt=0;
        }
    }
    cout<<ans;
    return 0;
}