HDU7174多校-Link with Bracket Sequence II

• 链接：http://acm.hdu.edu.cn/showproblem.php?pid=7174
• 知识点：区间DP、组合数学
• 难度：蓝

题意

• 给出一个长度为 $n(n\le 500)n(n\backslash leq500)$ 的序列和一个数字 $m(m\le 10^9)m(m\backslash leq10^9)$。
• 保证序列中的每个数字 $\mathrm{\mid }{a}_i\mathrm{\mid }\le m|a\_i|\backslash leq\; m$。
• 对于序列中每个0，需要填充一个绝对值 $\le m\backslash leq\; m$ 的数字。
• 要保证对于每个 $a_i>0a\_i\; >\; 0$，在它的右方总有一个 与之配对。
• 需要注意的是，不同成对的数字之间不允许交叉。例如：$1,2,-1,-21,2,-1,-2$ 是不合法的。
• $1,2,-2,-11,2,-2,-1$ ； $1,-1,2,-21,-1,2,-2$ ； $1,2,-2,-1,3,4,-4,-31,2,-2,-1,3,4,-4,-3$ 是合法的

思路

• DP。
• $mm$ 的范围过大，将它留在 DP 的状态中显然不合适，考虑在转移的时候将 $mm$ 的贡献乘进答案中。

错误思路1

• 线性DP。设状态为 $dp[i][j][k][p]dp[i][j][k][p]$ 为
• • $ii$：当前在第 $ii$ 位，
• • $jj$：当前还需要放 $jj$ 个负数与初始的正数配对，
• • $kk$：当前还需要放 $kk$ 个正数与初始的正数配对，
• • $pp$：当前放的既不与初始的正数配对也不与初始的负数配对的数字正数比负数多的数量
• 复杂度太大，转移非常繁琐。

错误思路2

• 区间DP。设状态为 $dp[l][r]dp[l][r]$
• 转移：
  • 如果当前区间左右两端分别为一正一负，或者一端为0一端非0： $dp[l+1][r-1]\to dp[l][r]dp[l+1][r-1]\; \backslash rightarrow\; dp[l][r]$
  • 如果当前区间左右两端均为0： $dp[l+1][r-1]\times m\to dp[l][r]dp[l+1][r-1]\backslash times\; m\; \backslash rightarrow\; dp[l][r]$
  • 对于所有情况，都有：$\sum dp[l][k]\times dp[k+1][r]\to dp[l][r]\backslash sum\; dp[l][k]\; \backslash times\; dp[k+1][r]\; \backslash rightarrow\; dp[l][r]$
• 错误原因：答案的累加出现了重复的情况。第三种转移出现了重复。

• 前置知识：去重问题
• 先看之前写的 牛客14599 - 子序列 的题解。https://blog.nowcoder.net/n/cca78595e55d4783ad5f78f9e058d20c

• 我们知道，涉及到去重问题，不妨从结果串下手。制定出一个匹配规则，使得按照这种规则寻找出的下标一定唯一。
• 这种规则可以是：设一个序列的最右侧的负数为$-x-x$，那么目标下标就是 $xx$ 的位置。
• 所以，避免重复出现的措施：却保k指针的左侧（或右侧）的区间的左右端点一定是成对的 即可。

正确思路

• 区间DP。设状态为 $dp[l][r][0\mathrm{/}1]dp[l][r][0/1]$代表区间 $[l,r][l,r]$ 的左右端点是否成对。
• 转移1:左右端点成对。
• 转移2:左右端点不成对，枚举中间指针k，$\sum (dp[l][k][0]+dp[l][k][1])\times dp[k+1][r][1]\to dp[l][r][0]\backslash sum\; (dp[l][k][0]+dp[l][k][1])\backslash times\; dp[k+1][r][1]\; \backslash rightarrow\; dp[l][r][0]$
• $ans=dp[1][n][0]+dp[1][n][1]ans=dp[1][n][0]+dp[1][n][1]$

代码

#include <cstdio>
#include <iostream>
typedef long long ll;
const int N		= 510;
const int MOD	= 1e9+7;
using namespace std;

int arr[N];
bool vis[N][N];
int dp[N][N][2];
int n,m;

bool Check(int l,int r)
{
	return (arr[l]>0 && arr[r]<0 && arr[r]==arr[l]*-1);
}

void DFS(int l,int r)
{
	if((r-l+1)&1)	return;
	if(vis[l][r])	return;
	vis[l][r] = true;
	
	if(r==l+1)
	{
		if(Check(l, r))	dp[l][r][1] = 1;
		else if(arr[l]==0&&arr[r]==0)	dp[l][r][1] = m;
		else if((arr[l]==0&&arr[r]<0)||(arr[r]==0&&arr[l]>0))	dp[l][r][1] = 1;
		return;
	}
	if(Check(l, r))
	{
		DFS(l+1, r-1);
		dp[l][r][1] = 1ll*(dp[l+1][r-1][0] + dp[l+1][r-1][1]) % MOD;
	}
	else if(arr[l]==0&&arr[r]==0)
	{
		DFS(l+1, r-1);
		dp[l][r][1] = 1ll*(dp[l+1][r-1][0] + dp[l+1][r-1][1]) % MOD * m % MOD;
	}
	else if((arr[l]==0&&arr[r]<0)||(arr[r]==0&&arr[l]>0))
	{
		DFS(l+1, r-1);
		dp[l][r][1] = 1ll*(dp[l+1][r-1][0] + dp[l+1][r-1][1]) % MOD;
	}
	
	ll sum = 0;
	for (int k=l; k<r; k++)
	{
		DFS(l, k);
		DFS(k+1, r);
		sum = (1ll* sum + 1ll*(dp[l][k][0]+dp[l][k][1]) % MOD * (dp[k+1][r][1]) % MOD)%MOD;
	}
	dp[l][r][0] = sum;
}

void Sol()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=i; j<=n; j++)
		{
			dp[i][j][0] = dp[i][j][1] = 0;
			vis[i][j] = 0;
		}
	}
	DFS(1, n);
	ll ans = 1ll*(dp[1][n][0] + dp[1][n][1]) % MOD;
	printf("%lld\n",ans);
}

signed main()
{
	int tt;
	scanf("%d",&tt);
	while (tt--)
	{
		scanf("%d %d",&n,&m);
		for (int i=1; i<=n; i++)
		{
			scanf("%d",&arr[i]);
		}
		Sol();
	}
	return 0;
}