关于字符串的简单dp

时间：2021-08-29 02:41:55

关于字符串的简单dp

看这道题题目叫做魔族密码多新奇的名字点开是道字符串的dp，思考然后想出lis其实但字符串之间的比对只有循环然后其实循环爆不了，太懒点开了题解发现有人使用stl——cstring的函数了方便多了，借鉴一下好啦。

函数：strncmp这个是cstring里对比两个字符串的东西从第一位开始对照相同则返回0，不同返回差值。

用法:strncmp(第一个字符串，第二个字符串，要比对的长度)；

然后还有返回字符串长度的东西strlen(某个字符串的长度)；这样加上lis就很好过啦。

然后scanf输入字符的时候，%s是输入字符串后面不加&，而%c输入单个字符后面加&。代码中将char类型直接当做字符串使用了，蒟蒻没见过的新操作诶，直接把char当做字符串。还有别忘了加string。字符串的题也得多做，要不容易遗忘一些简单的操作。

#include<iostream>

#include<cstdio>

#include<map>

#include<vector>

#include<iomanip>

#include<cmath>

#include<ctime>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<stack>

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

int n,ans=;

char s[maxn][];

int f[maxn];

int main()

{

    //freopen("1.in","r",stdin);

    n=read();

    for(int i=;i<=n;i++)scanf("%s",s[i]);

    for(int i=;i<=n;i++)f[i]=;

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

    {

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

        {

            if(strncmp(s[i],s[j],strlen(s[j]))==)

                f[i]=max(f[i],f[j]+);

        }

    }

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

        ans=max(ans,f[i]);

    printf("%d\n",ans);

    return ;

}

题交后wa了3个点发现自己赋初值赋的不对这个一定要注意每个f[i]都应该是1；失误。

不加函数的也就多了一个for循环而已。自己太懒啦。。。

#include<iostream>

#include<cstdio>

#include<map>

#include<vector>

#include<iomanip>

#include<cmath>

#include<ctime>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<stack>

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

int n,ans=;

char s[maxn][];

int f[maxn];

int main()

{

    //freopen("1.in","r",stdin);

    n=read();

    for(int i=;i<=n;i++)scanf("%s",s[i]);

    for(int i=;i<=n;i++)f[i]=;

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

    {

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

        {

            int flag=;

            for(int k=;k<strlen(s[j]);k++)

            {

                if(s[j][k]!=s[i][k])

                    flag=;

            }

            if(flag==)f[i]=max(f[i],f[j]+);

        }

    }

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

        ans=max(ans,f[i]);

    printf("%d\n",ans);

    return ;

}

谁的青春不曾有过潦草迷茫？

相关文章