P1415 拆分数列
斯德哥尔摩
2018-10-28 10:06:39
[P1415 拆分数列](https://www.luogu.org/problemnew/show/P1415)
第一步先求出最后的那个数最小为多少。
设$dp[i]$是处理到$i$时的最小末尾。
由于最小末尾是个很大的数，所以我们要用下标来表示出它。
而这个数一定在$i$终止，所以我们可以存它的起始位置。
于是重新定义状态：
设$dp[i]$是处理到$i$时的最小末尾的起始下标。
转移方程长这个样：
$$dp[i]=\max\{\ j\ |\ j\in[1,i],num(j,i)>num(dp[j-1],j-1)\ \}$$
注意那个数字比较大小记得处理前导零。
第二步要求最后一个数确定的情况下，前面的数字按字典序尽量大的解。
同上，设$f[i]$是从$n$处理到$i$时的最大末尾的结束下标。
转移方程：
$$f[i]=\max\{\ j\ |\ j\in[i,f[n]],num(i,j)<num(j+1,f[j+1])$$
初始化$f[dp[n]]=n$。
有一个坑点：$[1,9]$都不能与最后一个数合并成一个数，但是$0$可以。。。。
煮个栗子：
如果第一次$DP$计算出最小末尾为$50$，但输入是$\times\times\times...\times00050$。。。
这样上面的转移方程不会将$000$和$50$分成一组，因为$j\in[i,f[n]]$。
这样$000$所在状态就和状态定义不符，它没表示出最大末尾。
那不就凉了？
所以$DP$前要先将最后一个数的前导零全部特判。
复杂度$O(n^3)$。
然后站长lzn说：由于数据大部分为随机，实际运行效率接近$O(n^2)$。。。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#define MAXN 510
using namespace std;
int n;
int dp[MAXN],f[MAXN];
char str[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
int check(int l1,int r1,int l2,int r2){
if(r2==0)return 1;
string s1,s2;
while(str[l1]=='0')l1++;
while(str[l2]=='0')l2++;
for(int i=l1;i<=r1;i++)s1+=str[i];
for(int i=l2;i<=r2;i++)s2+=str[i];
if(s1.size()>s2.size())return 1;
else if(s1.size()<s2.size())return 0;
else{
if(s1==s2)return -1;
else return s1>s2;
}
}
void solve_one(){
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=i;j>=1;j--)if(check(j,i,dp[j-1],j-1)==1){
dp[i]=max(dp[i],j);
break;
}
}
}
void solve_two(){
int m=0;
f[dp[n]]=n;
for(int i=dp[n]-1;i&&str[i]=='0';i--){
f[i]=n;
m++;
}
for(int i=dp[n]-1-m;i>=1;i--){
f[i]=i;
for(int j=dp[n]-1;j>=i;j--)if(check(i,j,j+1,f[j+1])==0){
f[i]=max(f[i],j);
break;
}
}
}
void print(int l,int r){
for(int i=l;i<=r;i++)putchar(str[i]);
}
void work(){
int now=1;
solve_one();
solve_two();
while(now<=n){
print(now,f[now]);
now=f[now]+1;
if(now<=n)putchar(',');
}
putchar('\n');
}
void init(){
scanf("%s",str+1);
n=strlen(str+1);
}
int main(){
init();
work();
return 0;
}
```