P3058 [USACO12NOV] Balanced Cow Breeds G/S 题解
DengDuck
·
·
题解
不知道为啥我的代码格外短。
首先根据题目给出的定义，我们可以考虑进行一个转化，把左括号看成 1，右括号看成 -1，这样合法括号序列可以看成任意前缀和非负，区间和为 0 的序列。
我们由此可以列出一个 \mathcal O(n^3) 的动态规划方案：
转移如下：
$$
f_{i,j,k}=f_{i-1,j-A_i,k}+f_{i-1,j,k-A_i}
$$
边界条件为 $f_{0,0}=1$。
$A_i$ 表示经过转换之后我们的数组的第 $i$ 项。
其实有用的状态并不多，剪剪枝卡卡空间可以过。
但是这个时间复杂度不够优秀，我们考虑进一步化简。
我们发现对于一个 $i$ 而言，有用的 $j+k$ 是不变的，为数组 $A$ 的前 $i$ 项的前缀和，这点观察式子也可以发现。
所以我们只维护 $j$ 一维，保证 $k$ 不为负数即可。
$$
f_{i,j}=f_{i-1,j-A_i}+f_{i-1,j}
$$
$k$ 非负如何保证？我们发现 $k=sum-j$，其中 $sum$ 是当前前 $i$ 项的前缀和，我们只要保证 $j\leq sum$ 即可。
时间复杂度降为 $O(n^2)$。
```cpp
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=2e3+5;
const LL mod=2012;
LL n,f[N][N],sum,a[N];
char s[N];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)
{
if(s[i]=='(')a[i]=1;
else a[i]=-1;
}
f[0][0]=1;
for(int i=1;i<=n;i++)
{
sum+=a[i];
for(int j=0;j<=sum;j++)
{
f[i][j]=f[i-1][j];
if(0<=j-a[i])f[i][j]+=f[i-1][j-a[i]];
f[i][j]%=mod;
}
}
printf("%lld",f[n][0]);
}
```