[洛谷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) \mid a(i,j) > a(f[j-1], j-1),\ 1 \le j \le 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之间的数分开，最前面的数的结尾下标。
状态转移方程：

$$f2[i] = \max(j) \mid a(i,j) < a(f2[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<bits/stdc++.h>
using namespace std;
#define maxn 505

char 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

就是这个样子啦！