原题传送：http://www.spoj.pl/problems/SQRBR
动态规划。
设f[i][j]表示前i个位置在合法情况下缺少j个右括号的方案数。
转移方程为：
f[i][j] = f[i-1][j-1] (第i个地方必须为'[')
f[i][j] = f[i-1][j-1] + f[i-1][j+1] (分第i个位置放左括号和右括号的情况)
写的第一份代码不是很严谨，j-1变为负值，但spoj判ac了。
#include <stdio.h>
#include <string.h>
#define N 205 int f[N][N], n, k;
bool h[N]; int main()
{
int t, d;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &k);
memset(h, , sizeof h);
memset(f, , sizeof f);
f[][] = ;
for(int i = ; i <= k; i++)
{
scanf("%d", &d);
h[d] = ;
}
for(int i = ; i <= * n; i++)
{
for(int j = ; j <= * n; j++)
{
if(h[i])
{
f[i][j] = f[i-][j-];
}
else
{
f[i][j] = f[i-][j-] + f[i-][j+];
}
}
}
printf("%d\n", f[*n][]);
}
return ;
}
修改后为：
#include <stdio.h>
#include <string.h>
#define N 205 int f[N][N], n, k;
bool h[N]; int main()
{
int t, d;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &k);
memset(h, , sizeof h);
memset(f, , sizeof f);
f[][] = ;
for(int i = ; i <= k; i++)
{
scanf("%d", &d);
h[d] = ;
}
for(int i = ; i <= * n; i++)
{
for(int j = ; j <= * n; j++)
{
if(h[i])
{
if(j != )
f[i][j] = f[i-][j-];
else
f[i][j] = ;
}
else
{
if(j != )
f[i][j] = f[i-][j-] + f[i-][j+];
else
f[i][j] = f[i-][j+];
}
}
}
printf("%d\n", f[*n][]);
}
return ;
}