题解：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})

。

代码：

CPP

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

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

文章操作

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

题目传送门

代码：

相关推荐

评论

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