CodeForces - 1461B Find the Spruce(递推)

技术文章 6个月前 完美者
1,145 0

标签:can   name   href   def   题目   c++   tps   min   pru   

CF1461B Find the Spruce

题目大意:

求指定类型图案的数量。

思路:

一个很巧妙的递推式。

注意从下往上进行递推。

Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 510;

int n, m; 
char mp[N][N];
int dp[N][N];

int main() {
	int T; scanf("%d", &T);
	while (T--) {
		memset(dp, 0, sizeof(dp));
		int ans = 0;
		scanf("%d %d", &n, &m);
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				scanf(" %c", &mp[i][j]);
			}
		}
		for (int i = n; i >= 1; i--) {
			for (int j = 1; j <= m; j++) {
				if (mp[i][j] == ‘*‘) {
					dp[i][j] = 1;
					dp[i][j] += min(dp[i + 1][j - 1], min(dp[i + 1][j], dp[i + 1][j + 1]));
					ans += dp[i][j];
				}
			}	
		}
		// for (int i = 1; i <= n; i++) {
		// 	for (int j = 1; j <= k; j++) {
		// 		cout << dp[i][j] << " ";
		// 	}
		// 	cout << endl;
		// }
		cout << ans << endl;
	}
	return 0;
}

CodeForces - 1461B Find the Spruce(递推)

标签:can   name   href   def   题目   c++   tps   min   pru   

原文地址:https://www.cnblogs.com/Nepenthe8/p/14290412.html

版权声明:完美者 发表于 2021-01-19 11:39:58。
转载请注明:CodeForces - 1461B Find the Spruce(递推) | 完美导航

暂无评论

暂无评论...