本文共 2412 字，大约阅读时间需要 8 分钟。

[洛谷P1415] 拆分数列 解题思路

题目背景

因为某些申必原因被删除

题目描述

给出一列数字，需要你添加任意多个逗号将其拆成若干个严格递增的数。如果有多组解，则输出使得最后一个数最小的同时，字典序最大的解（即先要满足最后一个数最小；如果有多组解，则使得第一个数尽量大；如果仍有多组解，则使得第二个数尽量大，依次类推……）。

输入输出格式

输入格式：

共一行，为初始的数字。

输出格式：

共一行，为拆分之后的数列。每个数之间用逗号分隔。行尾无逗号。

输入输出样例

input

[1]

3456

[2]

3546

[3]

3526

[4]

0001

[5]

100000101

output

[1]

3,4,5,6

[2]

35,46

[3]

3,5,26

[4]

0001

[5]

100,000101

上面的样例是分开的！！因为懒，所以不想分开写。

【数据范围】

对于10%的数据，输入长度<=5

对于30%的数据，输入长度<=15 对于50%的数据，输入长度<=50 对于100%的数据，输入长度<=500

思路：

研究表明这道题用一个DP似乎是写不出来的。

所以我们为不把这道题分成几个小的DP？？

因为题目说首先保证最后的数尽量小，所以要先把最后一个数的最小值DP出来。设f[i]表示把第i个数之前的数分开，最后一个数的开始的下标。

很容易（难）想到状态转移方程：

f[i]=max(j)∣a(I,j)>a(f[j−1],j−1),1≤j≤i

代码：

for(int i=1;i<=n;i++)	{
   		f[i]=1;		for(int j=i;j>=1;j--)			if(pd(j,i,f[j-1],j-1)==1)			{
   				f[i]=max(f[i],j);				break;			}	}

pd那个函数是判断j~i组成的数是否比f[j-1],j-1之间的数大。

之所以j要从后往前枚举，是为了保证让它递增的尽量慢一些，这样才能保证最后一个数尽量小。

搞♂完以后，就是让第一个数以及后面的数尽量大啦！

为了让第一个数尽量大，那么就从后往前DP。 设f2[i]表示把i~n之间的数分开，最前面的数的结尾下标。 状态转移方程：

f[I]=max(j) | a(I,j)<a(f[j+1],j+1)

注意一下边界，f2[f[n]]=n

还有注意处理它前面的0(不然会GG）

code:

f2[f[n]]=n;	for(int i=f[n]-1;i&&a[i]==0;i--) f2[i]=n,cnt++;	for(int i=f[n]-1-cnt;i>=1;i--)	{
   		f2[i]=i;		for(int j=f[n]-1;j>=i;j--)		{
   			if(pd(i,j,j+1,f2[j+1])==0)			{
   				f2[i]=max(f2[i],j);				break;			}		}	}

这里的j也是从后往前枚举的。

是为了让它递减的慢一点，这样可以保证前面的数尽量大。

完整代码：

#include
   
    using namespace std;#define maxn 505char a1[maxn];int a[maxn],cnt;int f[maxn],n,f2[maxn];int pd(int l1,int r1,int l2,int r2){
   	while(a[l1]==0 && l1 < r1) l1++;	while(a[l2]==0 && l2 < r2) l2++;	if(r1-l1!=r2-l2)		return r1-l1 > r2-l2;	int To=r1-l1;	for(int i=0;i<=To;i++)		if(a[l1+i]!=a[l2+i])			return a[l1+i] > a[l2+i];	return -1;}inline void print(int l,int r){
   	for(int i=l;i<=r;i++)		printf("%d",a[i]);}int main(){
   	scanf("%s",a1+1);	n=strlen(a1+1);	for(int i=1;i<=n;i++)		a[i]=a1[i]-'0';	for(int i=1;i<=n;i++)	{
   		f[i]=1;		for(int j=i;j>=1;j--)			if(pd(j,i,f[j-1],j-1)==1)			{
   				f[i]=max(f[i],j);				break;			}	}	f2[f[n]]=n;	for(int i=f[n]-1;i&&a[i]==0;i--) f2[i]=n,cnt++;	for(int i=f[n]-1-cnt;i>=1;i--)	{
   		f2[i]=i;		for(int j=f[n]-1;j>=i;j--)		{
   			if(pd(i,j,j+1,f2[j+1])==0)			{
   				f2[i]=max(f2[i],j);				break;			}		}	}	int pos=1,flag=1;	while(pos<=n)	{
   		if(flag==1) flag=0;		else printf(",");		print(pos,f2[pos]);		pos=f2[pos]+1;	}	return 0;}
   

注意那个pd函数，之所以不开bool是因为排除两个数相等的尴尬情况

因为题目要求是严格递增的。所以第二个dp如果直接用的话 a<=b 的情况的就会直接转移了，从而得出错误的答案 不信试试这个 input

222222

output

2，22，222

就是这个样子啦！

转载地址：http://kyuci.baihongyu.com/