P1950 长方形

题目：

P1950 长方形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 

 算法：

dp动态规划

代码：

#include
#include
typedef unsigned long long ull;
const int N = 1010;
using namespace std;
 int r, c, i, j;
ull h[N][N], w[N][N];
int main()
{
	cin >> r >> c;
	string s;
	ull count = 0,sum=0;
	for (i = 1; i <= r; i++){
		cin >> s;
		for (j = 0; j < c; j++) {
			if (s[j] == '.') {
				h[i][j+1] = h[i - 1][j+1] + 1;
				w[i][j + 1] = w[i][j] + 1;
				sum += h[i][j + 1] + w[i][j + 1];
				count++;
			}
		}	
	}
	cout << sum - count;
}
//（自己编译器上能过，洛谷上一个都过不了。。。哪个大佬救救我啊啊啊）