menu Stephen Space
more_vert
chevron_right 首页 » 【OI】 » 正文
【OI】OI日记 · 8月3号——线性及区间DP
2020-08-03 | 【OI】 | 暂无评论 | 358 次阅读 | 302字

【OI】OI日记 · 8月3号——线性及区间DP
    DP是算法界的一个老法师,和其它任何东西都可以结合在一起。今天,我们以题目的方式来练习一下。

T1:括号匹配

问长度为N的完美括号匹配序列有多少种?答案对100000007取模。
数据范围:$N \leq 4000$

    首先,这一道题是一道线性DP,我们设$f[i][j]$,i为左括号个数,j为右括号个数,那么最终答案就是$f[N/2][N/2]$,因为最终左右括号数一定相等。然后,来处

理特殊情况。首先,我们要确保左括号的数量要大于等于右括号,因为最后一个放的始终是右括号,不然就没有合法序列。及:

$$ f(i,j) = \begin{cases} 0 &\quad (i<j) \end{cases} $$

然后,当j=0,也就是只有左括号没有右括号时,我们要设定成1,因为它在最有一定有一组合法序列,因为最后一个括号是右括号,所以公式再扩张:

$$ f(i,j) = \begin{cases} 0 &\quad (i<j) \\ 1 &\quad (j=0) \end{cases} $$

最后,就是加起来了。把少一个左括号与少一个右括号的加起来,及模拟增加一个括号。所以,最后转移公式如下:

$$ f(i,j) = \begin{cases} 0 &\quad (i<j) \\ 1 &\quad (j=0) \\ f[i-1][j]+f[i][j-1] &\quad (i \geq j) \end{cases} $$

最后的最后,把它打出来!代码很简单,给你们康康:

#include <bits/stdc++.h>
#define MAXN 4005
using namespace std;
int f[MAXN][MAXN];
int n;
int main()
{
    cin>>n;
    for (int i=0;i<=n;i++)
    for (int j=0;j<=n;j++)
    {
        if (j==0)
        {
            f[i][j]=1;
            continue;
        }
        if (i<j) continue;
        f[i][j]=f[i-1][j]+f[i][j-1];
    }
    cout<<f[n/2][n/2]<<endl;
    return 0;
}
None
发表评论
暂无评论
textsms
account_circle
email
link