Famil Door and Brackets codeforces dp

Famil Door and Brackets codeforces dp

好像我的dp方程和别人的不一样。。。。

这个dp方程有trick，容易出错

将s看做一个，总共的个数就为n-m+1

dp[i][j][0/1]:前i个，( 比  ) 多j个，0:s没有放置，1:s放置了

对于个i讨论是否为(,),s的情况

。。。。。

但是s是一个串所有必须满足s中每个位置都满足条件，就是针对情况s中"("个数减去")"的个数的最小值(min_dis)

dis:s串中"("个数减去")"的个数。

初始化的应该为if(dis>=0 && dis<=2000 && min_dis>=0)dp[1][dis][1]+=1;

转移方程的时候也要注意为s的时候哦。。。。

代码如下

/*
ID: meixiny1
PROG: test
LANG: C++11
*/
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#include <cctype>
using namespace std;
typedef long long ll;
typedef pair<int ,int> pii;
#define MEM(a,b) memset(a,b,sizeof a)
#define CLR(a) memset(a,0,sizeof a);
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
#define PI 3.1415926535898
ll dp[2005][2005][2];
int open,clse;
int main()
{//freopen(&#", "r", stdin);//freopen(&#","w",stdout);int n,m;scanf("%d%d",&n,&m);char s[200005];scanf("%s",s+1);int min_dis = inf,dis;for(int i=1;i<=m;i++){if(s[i]=='(')open++;else clse++;min_dis = min(min_dis,open-clse);}dis = open - clse;if(dis>=0 && dis<=2000 && min_dis>=0)dp[1][dis][1]+=1;dp[1][1][0]+=1;for(int i=2;i<=n-m+1;i++){for(int j=0;j<=2000;j++){//opendp[i][j+1][0]=(dp[i][j+1][0]+dp[i-1][j][0])%MOD;dp[i][j+1][1]=(dp[i][j+1][1]+dp[i-1][j][1])%MOD;//closeif(j){dp[i][j-1][0]=(dp[i][j-1][0]+dp[i-1][j][0])%MOD;dp[i][j-1][1]=(dp[i][j-1][1]+dp[i-1][j][1])%MOD;}//sif(j+min_dis>=0 && j+min_dis<=2000 && j+dis<=2000){dp[i][j+dis][1]=(dp[i][j+dis][1]+dp[i-1][j][0])%MOD;}}}cout << dp[n-m+1][0][1] << endl;return 0;
}