并不对劲的loj6191

传送门->

 设dp[i][j]表示考虑后i个人，栈里放了j个待匹配的括号时，期望匹配上多少括号。

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);i++)
#define dwn(i,x,y) for(register int i=(x);i>=(y);i--)
#define maxn 2010
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x*f;
}
void write(int x)
{
	int f=0;char ch[20];
	if(!x){putchar('0'),putchar('
');return;}
	if(x<0)x=-x,putchar('-');
	while(x)ch[++f]=x%10+'0',x/=10;
	while(f)putchar(ch[f--]);
	putchar('
');
}
int n;
double dp[maxn][maxn];
int main()
{
	n=read();
	dwn(i,n-1,0)
		rep(j,0,n)
		{
		    if(j!=0)dp[i][j]=0.5*(dp[i+1][j+1])+0.5*(dp[i+1][j-1]+2);
		    else dp[i][j]=0.5*(dp[i+1][j+1])+0.5*(dp[i+1][j]);
		}
	printf("%.3lf",n*1.0-dp[0][0]);
	return 0;
}