P6388LEKTIRA 字符串DP 题解

· · 题解

P6388

题意简述：

将一个字符串分成三段，把每一段倒过来拼成一个新字符串，求字典序最小的一个新字符串

字符串长度 3 \leq n \leq 50

这题十分玄学，有两种正解

为了便于分析，设分成的段数为k

分段做法 ：

搜索枚举每一次分段的分段位置，找出结果最小的一个

所有分段可能数目大体相当于在n个物品里选k-1个物品方案数目

大概=n^{k-1}，处理结果时O(n)，所以综合复杂度O(n^k)，

DP做法

我们知道，DP就是记忆化搜索，也就是改进的爆搜

设f[i][j]为从i开始到结尾，一共用j次分段的最小字典序

我们枚举这一段结尾的字符位置l

则f[i][j]=min(f[i][j],u+f[l+1][j-1])(i \leq l \leq n-1-j)

其中u是自i到l的回文

枚举i,j,l为O(kn^2)，而处理u为O(n)

综合复杂度为O(kn^3)

现在，来到这道题精髓的地方，将k=3带回原式。

DP做法复杂度=O(3*n^3)，约O(n^3)

看上去很烂的分段是O(n^3)

也就是说，看上去烂的算法在这道题里跑的挺快！

经过实际测试，DP做法是一共20ms，而分段算法是19ms！快了1ms！所以这题很玄学

注意事项：

截取原来的字符串可以使用string的substr函数，这个函数用法是

a.substr(开始位置,截取字符数);

反转字符串可以用algorithm的reverse函数，这个函数用法是

reverse(a.begin(),a.end());

现在把两种AC代码全部放上

DP做法：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

string f[100][5];
string a;
string u;
int main(){
    cin>>a;
    int n=a.size();
    int k=3;
    for(int i=n-1;i!=-1;i--){
        u=a.substr(i,n-i);
        reverse(u.begin(),u.end());
        f[i][0]=u; 
        for(int j=1;j<k;j++){ 
            f[i][j]="|";
            for(int l=i;l<=n-1-j;l++){ 
                string u=a.substr(i,l-i+1);
                reverse(u.begin(),u.end());
                f[i][j]=min(f[i][j],u+f[1+l][j-1]);
            }
        }
    }
    cout<<f[0][k-1];
}

分段算法：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

string mi,a;
int n,k;
int f[1000];

void ch(){
    string a1,a2;
    a2.clear();
    int p=0;
    for(int i=1;i<=k;i++){
        a1=a.substr(p,f[i]-p);
        reverse(a1.begin(),a1.end());
        a2=a2+a1;
        p=f[i];
    }
    mi=min(mi,a2);
}

int sou(int m,int c){
    if(c==3){
        ch();return 0;
    }
    for(int i=m;i<=n-k+c;i++){
        f[c]=i;
        sou(i+1,c+1);
    }
    return 0;
}

int main(){
    mi="|";
    cin>>a;
    n=a.size();
    k=3;
    f[k]=n;
    sou(1,1);
    cout<<mi;
    return 0;
}

感谢大家观赏！

希望不要抄袭