Codeforces611CNewYearandDominoDP+前缀和

点击打开链接

题意:

• 给你个矩阵，每个位置是空或者不空
• 每两个相邻空的位置，可以放一个木条
• 有q次询问，每次问你一个子矩阵中，放一根木条有多少种放法

定义好状态即可:/f[i][j] 第i行横着放,前j列&&以第j列为终点(第2个'.'在第j列上)连续2个.的个数 

//cos A=(b2+c2-a2)/2bc
#include 
typedef long long ll;
using namespace std;
const int N=6e2+20;
char g[N][N];
int h,w;
int f[N][N],d[N][N];//f[i][j] 第i行横着放,前j列&&以第j列为终点(第2个'.'在第j列上)连续2个.的个数 

void init()
{
	memset(f,0,sizeof(f));
	memset(d,0,sizeof(d));
	for(int i=1;i<=h;i++)
	{
		f[i][0]=0;
		f[i][1]=0;
		for(int j=2;j<=w;j++)
		{
			if(g[i][j]=='.'&&g[i][j-1]=='.')
			f[i][j]=f[i][j-1]+1;
			else
			f[i][j]=f[i][j-1];
		
			//cout<