管道取珠[NOIP2009]

题目链接:https://www.luogu.com.cn/problem/P1758

对于管道取珠[NOIP2009]的理解:

假定有两个人(记作甲和乙)在同时进行取珠子的操作,并且两个人取出来的珠子的序列完全相同,那么他们两个人的同步操作方案数即为所求。

下面用动态规划解决这个问题:

状态表示:

管道取珠[NOIP2009]代表甲在上管道已经取出管道取珠[NOIP2009]个,在下管道已经取出管道取珠[NOIP2009]个,乙在上管道已经取出管道取珠[NOIP2009]个,在下管道已经取出管道取珠[NOIP2009]时总的方案数目。

两个人取出珠子序列完全相同意味着必然有管道取珠[NOIP2009]

为了讨论方便,我们将字符数组进行翻转。

状态计算:

通常来说,状态计算分为两种:

管道取珠[NOIP2009]考虑当前状态如何由其它状态转移过来(入边);

管道取珠[NOIP2009]考虑如何由当前状态转移到相关状态(出边)。

这道题我们采用第二种方式:

让甲乙两个人同时取出一个珠子(为了二人序列相同,此时取出来的珠子必须相同)

管道取珠[NOIP2009]有可能转移到的状态有:

管道取珠[NOIP2009]:前提是管道取珠[NOIP2009],否则这个时候两个人产生的序列不相同。

管道取珠[NOIP2009]:前提是管道取珠[NOIP2009],原因同上。

管道取珠[NOIP2009],管道取珠[NOIP2009]类似。

下面这幅图可以帮助理解:

管道取珠[NOIP2009]

图片对应于第一种转移。

由于管道取珠[NOIP2009]除了由当前的管道取珠[NOIP2009]转移过来,还可能从其他方式转移过来,但是我们考虑的是出边的计算方式,所以具体方程应该是:

管道取珠[NOIP2009]

经过分析,思路算是比较明确了,下面就是代码的实现:

由于管道取珠[NOIP2009]成立管道取珠[NOIP2009]的值可以由管道取珠[NOIP2009]唯一确定,因此代码实现时可以略去一个维度。

下面贴出没有优化的代码。

#include<bits/stdc++.h>
using namespace std;

const int N = 510;
int n, m;
int dp[N][N][N];
char a[N], b[N];
#define mod 1024523

int main()
{
	cin>>n>>m;
	for(int i = 1;i <= n; i++)cin>>a[i];
	for(int i = 1;i <= m; i++)cin>>b[i];
	reverse(a + 1, a + n + 1);
	reverse(b + 1, b + m + 1);
	
	dp[0][0][0] = 1;
	for(int i = 0;i <= n;i++)
	{
		for(int j = 0;j <= m; j++)
		{
			for(int k = 0;k <= n ;k++)
			{
				int t = dp[i][j][k];
				int l = i + j - k;
				if(l < 0 || l > m)continue;//非法情况
				if(a[i + 1] == b[l + 1])dp[i + 1][j][k] = (t + dp[i + 1][j][k])%mod;
				if(a[i + 1] == a[k + 1])dp[i + 1][j][k + 1] = (t + dp[i + 1][j][k + 1])%mod;
				if(b[j + 1] == a[k + 1])dp[i][j + 1][k + 1] = (t + dp[i][j + 1][k + 1])%mod;
				if(b[j + 1] == b[l + 1])dp[i][j + 1][k] =(t + dp[i][j + 1][k])%mod;
			}
		}
	}
	
	cout<<dp[n][m][n];
	return 0;
}

优化

考虑空间优化

注意到每次进行状态转移时i的值只是与奇偶性相关,也就是说整个dp数组实际上有用的信息就只有两层:当前状态与上一层状态。

两种滚动数组的方法:

管道取珠[NOIP2009]用i&1进行奇偶层次的区分

管道取珠[NOIP2009]额外加一个自变量cur,并且每次与1进行异或运算(相当于flip操作)。

 第一种:

#include<bits/stdc++.h>
using namespace std;

const int N = 510;
int n, m;
int dp[N][N][N];
char a[N], b[N];
#define mod 1024523

int main()
{
	cin>>n>>m;
	for(int i = 1;i <= n; i++)cin>>a[i];
	for(int i = 1;i <= m; i++)cin>>b[i];
	reverse(a + 1, a + n + 1);
	reverse(b + 1, b + m + 1);
	
	dp[0][0][0] = 1;
	for(int i = 0;i <= n;i++)
	{
		for(int j = 0;j <= m; j++)
		{
			for(int k = 0;k <= n ;k++)
			{
				int t = dp[i&1][j][k];
				int l = i + j - k;
				if(l < 0 || l > m)continue;//非法情况
				if(a[i + 1] == b[l + 1])dp[(i + 1)&1][j][k] = (t + dp[(i + 1)&1][j][k])%mod;
				if(a[i + 1] == a[k + 1])dp[(i + 1)&1][j][k + 1] = (t + dp[(i + 1)&1][j][k + 1])%mod;
				if(b[j + 1] == a[k + 1])dp[i&1][j + 1][k + 1] = (t + dp[i&1][j + 1][k + 1])%mod;
				if(b[j + 1] == b[l + 1])dp[i&1][j + 1][k] =(t + dp[i&1][j + 1][k])%mod;
				dp[i&1][j][k] = 0;//为了防止干扰下一层的计算,清零。
			}
		}
	}
	
	cout<<dp[(n + 1)&1][m][n];
	return 0;
}
上一篇:对list集合重新排序


下一篇:【LeetCode题解】字符串乘法、加法