题目

给定一个长度为n(n<=5000)的由['0'..'9']组成的字符串s，v[i,j]表示由字符串s第i到第j位组成的十进制数字。

将它的某一个上升序列定义为：将这个字符串切割成m段不含前导'0'的串，切点分别为k1,k2...km-1，使得v[1,k1]<v[k1+1,k2]<...<v[km-2,km-1]。

请你求出该字符串s的上升序列个数，答案对 10^9+7 取模。

题解

对于这种dp题，如果没有思路，我们可以先从最暴力的搜索开始分析，然后逐步优化

版本1

深搜枚举每一段的起点，搜完后逐段验证。

版本2

发现只要记录当前起点，终点，就可以描述出所有的后续状态，从而实现记忆化搜索。

版本3

把深搜改造成从后往前的dp,开两维记录起点、终点。时间复杂度：$O(n^3)$

版本4

把匹配过程改进，通过dp预处理出所有串的lcp，将匹配过程跳至不相等处。时间复杂度：$O(n^2)$

总结

设发$f[i][j]$表示起点为i,区间长度为j的方案数

那么本段范围为$[i,i+j)$,下一段的终点$>=i+j*2-1$

考虑状态转移：

若当前段比下一段小，则

$f[i][j] = f[i+j][j] + f[i+j][j+1] + ... + f[i+j][n-i]$

否则

$f[i][j] = f[i+j][j+1] + f[i+j][j+2] + ... + f[i+j][n-i]$

但是如果这样枚举会变成$O(n^3)$

我们可以使用后缀和来加速过程。

代码

#include <iostream>

#include <cstdio>

#define N 5001

#define int long long

#define mod (int)1e9+7

using namespace std;

char str[N];

int dp[N][N],n,lcp[N][N];

int compare(int a,int b)

{

	int t=min(lcp[a][b],b-a-1);

	return str[a+t]<str[b+t];

}

signed main()

{

	cin>>n;

	scanf("%s",str+1);

	for(int i=n;i;i--)//lcp[i][j]表示从str[i,n]和str[j,n]的lcp

	{

		for(int j=i+1;j<=n;j++)

		{

			if(str[i]==str[j]) lcp[i][j]=lcp[i+1][j+1]+1;

		}

	}

	for(int i=n;i;i--)//枚举起点

	{

		if(str[i]=='0') continue;

		dp[i][n-i+1]=1;//起点到n划为一块

		for(int j=1;j<=n-i;j++)//枚举区间长度，同时也是下一个起点的位置

		{

			if(compare(i,i+j)) dp[i][j]=dp[i+j][j];//等同于公式1

			else dp[i][j]=dp[i+j][j+1];//等同于公式2

		}

		for(int j=n-i;j;j--)//维护后缀和

		{

			//cout<<dp[i][j]<<" ";

			dp[i][j]+=dp[i][j+1],dp[i][j]%=mod;

		}

		//cout<<endl;

	}

	cout<<dp[1][1];

}

巴特西

【测试题】sequence

题目

题解

版本1

版本2

版本3

版本4

总结

代码

最新文章

热门文章