P1950 长方形

长方形"/>

P1950 长方形

题目：

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

 算法：

dp动态规划

代码：

#include<iostream>
#include<string>
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;
}
//（自己编译器上能过，洛谷上一个都过不了。。。哪个大佬救救我啊啊啊）