有一些区间dp的区间中有可能出现重复的东西,因此这样的话我们就不能用正常的二维数组来写,我们还需要加上去重的东西
例题1
Connecting Vertices CF888F
题面翻译
有一个正 $N$ 边形,顶点顺时针编号为 $1\sim N$。问用 $N - 1$ 条线段连接这 $N$ 个顶点,使它们连成一棵树,有多少种方法。
连边时有以下限制:
-
给出一个 $N \times N$ 的 $01$ 矩阵 $A$,$A_{i,j}= 1$ 表示顶点 $i$ 和顶点 $j$ 可以直接相连,而 $A_{i,j}=0$ 时则不能。保证了 $A_{i,i}= 0$,$A_{i,j}=A_{j,i}$。
-
两条线段不能在顶点之外的地方相交,如不能同时连 $(1,3)$ 和 $(2,4)$。
样例输入
3
0 0 1
0 0 1
1 1 0
样例输出
1
分析
这道题不能同时连 $(1,3)$ 和 $(2,4)$,因此区间不相交,可以想到是区间dp
-
首先我们用基本的区间dp来求解可以将l和r是否相连分成两类
-
要是l和r可以直接相连,那么dp[l][r]+=dp[l][k]*dp[k+1][r]
-
然后l和r不相连,即l和r中间需要一个点来将这两边连接在一起,那么dp[l][r]+=dp[l][k]*dp[k][r];
-
但是在第二点的时候我们发现前面用一个中转点连在一起,后面一部分也可以用一个中转点p连在一起,那遍历到p这个位置时相当于再算了一遍,因此我们还得把这个状态拆分开来变成dp[l][r][2],0表示不用中转点,1表示要中转点,然后二者相加就是最终答案
-
因此
dp[l][r][0]+=(dp[l][k][0]+dp[l][k][1])*(dp[k+1][r][0]+dp[k+1][r][1])
相当于之前的状态不变 -
dp[l][r][1]+=dp[l][k][0]*(dp[k][r][0]+dp[k][r][1])
相当于前一部分不能用中转点,后一部分随意,这样就可以做到不重不漏
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 510,mod=1e9+7;
int a[N][N];
int dp[N][N][2];//0表示可以直接lr可以直接相连,1表示lr之间要加一个点才能相连
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
for(int i=1;i<=n;i++) dp[i][i][0]=1;
for(int len=2;len<=n;len++)
{
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
for(int k=l;k<r;k++)
{
if(a[l][r]) dp[l][r][0]=(dp[l][r][0]+1ll*(dp[l][k][0]+dp[l][k][1])*(dp[k+1][r][0]+dp[k+1][r][1]))%mod;
if(k>l) dp[l][r][1]=(dp[l][r][1]+1ll*dp[l][k][0]*(dp[k][r][0]+dp[k][r][1]))%mod;
}
}
}
cout<<(dp[1][n][0]+dp[1][n][1])%mod<<endl;
}
例题2
Link with Bracket Sequence II 杭电多校4—1001
题面翻译
有一个长度为n的括号序列,x代表当前括号是x类型的左括号,-x代表当前是x类型的右括号,并且括号一共有m种,求这个序列有几种方案数
样例输入
3
4 2
1 0 0 -1
4 2
0 0 0 -1
6 3
0 0 0 0 0 0
样例输出
3
4
135
分析
这道题括号有m种,然后题中给出了几个位置的括号是什么,由于不同括号不能交叉放置,因此这题区间不相交,是区间dp问题
- 首先我们用基本的区间dp来求解可以将l和r是否匹配分成两类
-
要是l和r可以匹配,那么dp[l][r]+=dp[l+1][r-1]*k(z这里的k是l和r的种类数)
-
然后l和r不匹配,即这个序列是一个并列的括号序列,dp[l][r]+=dp[l][k]*dp[k+1][r]
-
但是在第二点的时候我们前面分出了一块[l,k]是合法序列,后面[k+1,r]还是有可能是并列的序列,那么k遍历到后面前面就有可能是并列的,那么就重复计算了,因此我们再开一维dp[l][r][2]——0表示l到r合法序列的方案数,1表示l到r且l和r匹配的合法方案数
-
因此
dp[l][r][1]=dp[l+1][r-1][0]*k
相当于之前的状态不变 -
dp[l][r][0]+=dp[l][k-1][0]*dp[k][r][1]
相当于前一部分任意,后一部分一定是l和r匹配上的情况,这样就保证了不会重复
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 510,mod=1e9+7;
typedef long long ll;
ll dp[N][N][2];//0表示l到r合法序列的方案数,1表示l到r且l和r匹配的合法方案数
int a[N];
int main()
{
//ios::sync_with_stdio(0),cin.tie(0);
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
memset(dp, 0, sizeof dp);
for(int i=1;i<=n;i++) cin>>a[i];
if(n&1){puts("0");continue;}
for(int i=0;i<=n;i++) dp[i+1][i][0]=1;
for(int len=2;len<=n;len+=2)
{
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
if(a[l]>=0&&a[r]<=0)
{
if(!a[l]&&!a[r]) dp[l][r][1]=dp[l+1][r-1][0]*m%mod;
else if(!a[l]||!a[r]||(a[l]+a[r]==0)) dp[l][r][1]=dp[l+1][r-1][0]%mod;
else dp[l][r][1]=0;
}
for(int k=l;k<=r;k+=2) dp[l][r][0]=(dp[l][r][0]+dp[l][k-1][0]*dp[k][r][1])%mod;
}
}
cout<<dp[1][n][0]<<endl;
}
}