luoguP1415 拆分数列 [dp]

题目描述

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

输入输出格式

输入格式：

共一行，为初始的数字。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

[1]

3,4,5,6

[2]

35,46

[3]

3,5,26

[4]

0001

[5]

100,000101

说明

【题目来源】

lzn改编

【数据范围】

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

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

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

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

《拆分数列》解题报告

By lzn 动态规划常规题。

第一步先求出最后的那个数最小为多少。（为了叙述方便，记T(i,j)表示从原数列下标i取到j的数字组成的数。）只需正向dp一次，dp1[i]表示前i个数字分成任意多个递增数且最后的数最小时，最后的数为T(dp1[i],i)。则dp1[i]=max(j)，(T(dp1[j-1],j-1)<T(j,i))。

第二步要求最后一个数确定的情况下，前面的数字按字典序尽量大的解。类似上面的方法反向动归一次即可。

算法复杂度o(l^3)。由于数据大部分为随机，实际运行效率接近l^2。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<string>

 using namespace std;

 const int maxn=;

 string str;

 int a[maxn],n,dP[maxn],Dp[maxn];

 bool cmp(int l1,int r1,int l2,int r2){

     while(l1<=r1&&a[l1]==)  l1++;

     while(l2<=r2&&a[l2]==)  l2++;

     int le1=r1-l1+,le2=r2-l2+;

     if(le1==||le2==)  return ;

     if(le1!=le2)  return le1<le2;

     for(int i=;i<le1;i++)

         if(a[l1+i]!=a[l2+i])  return a[l1+i]<a[l2+i];

     return ;

 }

 //dP[i]=max(j)，(T(dP[j-1],j-1)<T(j,i))

 void DP1(){

     for(int i=;i<=n;i++){

         dP[i]=;

         for(int j=i;j;j--)

             if(cmp(dP[j-],j-,j,i)){

                 dP[i]=j;

                 break;

             }

 //        printf("dP[%d] = %d\n",i,dP[i]);

     }

 }

 //Dp[i]=max(j)   (T(i,j)<T(j+1,f[j+1]))

 void DP2(){

     Dp[dP[n]]=n;

     for(int i=dP[n];a[i-]==;i--)  Dp[i-]=n;

     for(int i=dP[n]-;i;i--){

         for(int j=dP[n]-;j>=i;j--)

             if(cmp(i,j,j+,Dp[j+])){

                 Dp[i]=j;

                 break;

             }

 //        printf("Dp[%d] = %d\n",i,Dp[i]);

     }

 }

 void print(int l,int r){

     for(int i=l;i<=r;i++)

         putchar(a[i]+'');

 }

 void print(){

     print(,Dp[]);

     int pos=Dp[]+;

     while(pos<=n){

         putchar(',');

         print(pos,Dp[pos]);

         pos=Dp[pos]+;

     }

 }

 int main(){

     cin>>str;  n=str.length();

     for(int i=;i<n;i++)  a[i+]=str[i]-'';

     DP1();  DP2();

     print();

     return ;

 }

巴特西

luoguP1415 拆分数列 [dp]

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章