题解

257 条题解

  • 8
    @ 2017-10-03 11:23:58

    最长上升子序列 (LIS)

    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 2010;
    int n, res, dp[maxn];
    string s[maxn];
    
    int main() {
        ios::sync_with_stdio(false);
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> s[i];
            dp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (s[i].find(s[j]) == 0) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }
        cout << res << endl;
        return 0;
    }
    
  • 3
    @ 2018-09-05 15:02:29

    字符串的题当然用hash啦
    加一个长度进行判断,精确度上不亚于双模

    #include<iostream>
    #include<cstring>
    using namespace std;
    char a[80];
    long long hash1[2010];
    int chang[2010],dp[2010];
    int main()
    {
        int n,i,len,j,k,ans=0;
        long long now,mo;
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>a;
            len=strlen(a);
            now=0;
            mo=1;
            for(j=0;j<len;j++)
            {
                now+=(a[j]-'a'+1)*mo;
                mo*=26;
                for(k=1;k<i;k++)
                 if(chang[k]==j+1)
                  if(hash1[k]==now)
                   dp[i]=max(dp[i],dp[k]+1);
            }
            chang[i]=len;
            hash1[i]=now;
            ans=max(ans,dp[i]);
        }
        cout<<ans+1;
        return 0;
    }
    
  • 2
    @ 2018-08-02 20:19:40

    trie树解法
    常规操作建树,在每个单词末位打标记,后续单词扫到的时候计数++,最后找最大就行了

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    int read(){
        int x=0,f=1;char c;
        for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
        for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-'0';
        return x*f;
    }
    int n;
    int top=0,tot=0,maxx=0;
    int num[2005];
    char s[100];
    struct node{
        int son[30];
        int end;
    }tr[5000005];
    void build_tr(){
        int len=strlen(s);
        int pos=0;top++;
        for(int i=0;i<len;i++){
            if(!tr[pos].son[s[i]-'a']){
                tr[pos].son[s[i]-'a']=++tot;
            }
            pos=tr[pos].son[s[i]-'a'];
            if(tr[pos].end==1)num[top]++;
        }
        tr[pos].end=1;
        num[top]++;
        maxx=max(maxx,num[top]);
    }
    int main(){
        n=read();
        for(int i=1;i<=n;i++){
            scanf("%s",s);build_tr();
        }cout<<maxx<<endl;
    }
    
    • @ 2019-06-03 17:54:40

      为什么运行时错误???数组开那么大干什么呢?

  • 2
    @ 2017-07-24 16:20:49

    //简单的dp,lcs问题
    //使用str查找函数来标记词链是一个巧妙的思路
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<string>
    #include<iostream>
    using namespace std;
    int n;
    int f[3000];
    string s[3000];
    int main()
    {

    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
    cin>>s[i];
    }
    for (int i=1;i<=n;i++)
    { f[i]=1;
    for (int j=1;j<i;j++)
    {

    if (s[i].find(s[j])==0)
    {
    f[i]=max(f[i],f[j]+1);
    }

    }
    }
    int ans=-1;
    for (int i=1;i<=n;i++)
    ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
    }

  • 1
    @ 2020-03-02 03:51:19

    #include <iostream> //魔族密码
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int MaxN = 2010;

    int N;
    int dp[MaxN];
    char word[MaxN][80];

    void DP()
    {
    int max = 1;
    char ch = word[0][0];
    for (int i = 1; i < N; i++)
    {
    if (word[i][0] != ch)
    {
    ch = word[i][0];
    continue;
    }
    for (int j = i - 1; word[j][0] == ch && j >= 0; j--)
    if (strstr(word[i], word[j]))
    {
    dp[i] = dp[j] + 1;
    if (max < dp[i])
    max = dp[i];
    break;
    }
    }
    printf("%d\n", max);
    }

    int main()
    {
    cin >> N;
    for (int i = 0; i < N; i++)
    {
    cin >> word[i];
    dp[i] = 1;
    }

    DP();

    system("pause");
    return 0;
    }

  • 1
    @ 2017-05-07 13:00:36
    /*
    LIS问题~
    其实说白了LIS就是满足条件找一条最长链而已
    或者换句话说这个题目就是一个DAG上的动态规划
    和lrj的紫书的嵌套矩形本质是一样的
    所以我们只需要判断一下两个单词是否可以链接
    因为注意到我们是要严格按照顺序来的
    所以我们完全没有必要去建图~
    因为两个单词本来最多就只会比较一次
    建图反而效率会更低
    这样我们就可以直接沿用LIS的模式
    只是判断大小变成了是否可以链接
    进行尝试转移就好了~
    QAQ总体还是挺简单的
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    string a[2003];
    int f[2003];
    int ans;
    int n;
    
    int check(int x,int y)//检查a[y]是否可以连在a[x]上
    {
        int l1=a[x].length();
        int l2=a[y].length();
        if(l1<=l2)
            return 0;
        for(int i=0;i<l2;i++)
            if(a[x][i]!=a[y][i])
                return 0;
        return 1;
    }
    
    void init()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            cin>>a[i];
    }
    
    void DP()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=i-1;j>=0;j--)//逆序尝试是否可以接在前面的某个string上
                if(check(i,j))
                    f[i]=max(f[i],f[j]+1);
            ans=max(ans,f[i]);
        }
        cout<<ans<<endl;
    }
    
    int main()
    {
        init();
        DP();
    }
    /*
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=2005;
    string a[MAXN];
    int f[MAXN];
    int g[MAXN][MAXN];
    int n;
    
    int check(int x,int y)
    {
        int l1=a[x].length();
        int l2=a[y].length();
        if(l1<=l2)
            return 0;
            for(int i=0;i<l2;i++)
            if(a[x][i]!=a[y][i])
                return 0;
        return 1;
    }
    
    int main()
    {
        int ans=-999;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(check(i,j))
                    g[i][j]=1;
        for(int i=1;i<=n;i++)
        {
            f[i]=1;
            for(int j=i-1;j>=0;j--)
                {
                    if(g[i][j])
                    f[i]=max(f[i],f[j]+1);
                }
            ans=max(ans,f[i]);
        }
        cout<<ans<<endl;
        return 0;
    }  
    */   
    
  • 1
    @ 2016-11-15 18:02:12

    单调栈做法
    ```c++
    #include <string>
    #include <iostream>
    #include <stack>
    using namespace std;

    stack<string> s;
    string a[1005];
    int n,ans=0;

    bool is_ok(string t)
    {
    if (s.empty()||t.substr(0,s.top().size())==s.top())
    return true;
    else
    return false;
    }

    int main(int argc, char const *argv[])
    {
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
    string t;
    cin>>t;
    while(!is_ok(t))
    s.pop();
    s.push(t);
    if (s.size()>ans)
    ans=s.size();
    }
    cout<<ans;
    return 0;
    }
    ```

    • @ 2018-07-19 15:51:00
      #include <string>
      #include <iostream>
      #include <stack>
      using namespace std;
      stack<string> s;
      string a[1005];
      int n,ans=0;
      bool is_ok(string t)
      {
          if (s.empty()||t.substr(0,s.top().size())==s.top())
              return true;
          else
              return false;
      }
      int main(int argc, char const *argv[])
      {
      cin>>n;
      for (int i = 0; i < n; ++i)
      {
          string t;
          cin>>t;
          while(!is_ok(t))
              s.pop();
          s.push(t);
          if (s.size()>ans)
              ans=s.size();
          }
          cout<<ans;
          return 0;
      }
      
  • 0
    @ 2020-10-29 10:57:41

    #include<iostream>
    #include <algorithm>
    using namespace std;
    #include<string>
    string Arr[2005];
    int main()
    {
    int n;
    int max = 1;
    int sum = 1;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
    cin >> Arr[i];
    }
    sort(Arr, Arr + n);

    for (int i = 1; i < n; i++)
    {
    sum = 1;
    for (int j = 0; j < i; j++)
    {
    if (Arr[i].compare(0, Arr[j].length(), Arr[j], 0, Arr[j].length()) == 0)
    {
    sum += 1;
    }
    }
    if (max < sum)
    max = sum;
    }
    cout << max<< endl;
    }

  • 0
    @ 2020-10-26 22:09:35

    #include<iostream>
    #include <algorithm>
    using namespace std;
    #include<string>
    string Arr[2005];
    int main()
    {
    int n;
    int max = 1;
    int sum = 1;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
    cin >> Arr[i];
    }
    sort(Arr, Arr + n);

    for (int i = 1; i < n; i++)
    {
    sum = 1;
    for (int j = 0; j < i; j++)
    {
    if (Arr[i].compare(0, Arr[j].length(), Arr[j], 0, Arr[j].length()) == 0)
    {
    sum += 1;
    }
    }
    if (max < sum)
    max = sum;
    }
    cout << max<< endl;
    }

  • 0
    @ 2020-10-26 22:08:18

    #include<iostream>
    #include <algorithm>
    using namespace std;
    #include<string>
    string Arr[2005];
    int main()
    {
    int n;
    int max = 1;
    int sum = 1;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
    cin >> Arr[i];
    }
    sort(Arr, Arr + n);

    for (int i = 1; i < n; i++)
    {
    sum = 1;
    for (int j = 0; j < i; j++)
    {
    if (Arr[i].compare(0, Arr[j].length(), Arr[j], 0, Arr[j].length()) == 0)
    {
    sum += 1;
    }
    }
    if (max < sum)
    max = sum;
    }
    cout << max<< endl;
    }//俺也不知道你们为啥那么复杂

  • 0
    @ 2020-05-21 21:40:28
    #include<iostream>
    #include<stdio.h>
    #include<string.h>
    using namespace std;
    int n,i,j,k,x,y,z;
    char ch[2001][100];
    int f[2001];
    bool swi;
    int main(){
        cin>>n;
        for(i=1;i<=n;i++){
            cin>>ch[i];
            f[i]=1;
            for(j=1;j<i;j++){
                swi=false;
                x=strlen(ch[j]);
                for(k=0;k<x;k++){
                    if(ch[j][k]!=ch[i][k]){
                        swi=true;
                        break;
                    }
                }
                if(!swi){
                    f[i]=f[i]>f[j]+1?f[i]:(f[j]+1);
                }
            }
            y=y>f[i]?y:f[i];
        }
        cout<<y<<endl;
        return 0;
    }
    
  • 0
    @ 2019-03-09 16:53:26

    用string类

    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<iostream>
    using namespace std;
    int N,dp[2005],m;
    string s[2005];
    int main(){
        ios::sync_with_stdio(false);
        cin>>N;
        for(int i=1;i<=N;i++){
            cin>>s[i];
            dp[i] = 1;
        }
        for(int i=2;i<=N;i++){
            for(int j=1;j<i;j++){
                if(s[i].find(s[j],0)==0)
                    dp[i] = max(dp[i],dp[j]+1);
            }
        }
        for(int i=1;i<=N;i++) m = max(m,dp[i]);
        cout<< m;
    }
    
    
    
  • 0
    @ 2017-09-02 22:53:01

    var
    a:array [1..2000] of string;
    b:array [1..2000] of longint;
    i,j,k,n,m,s,t:longint;
    function max(x,y:longint):longint;
    begin
    if x>y then max:=x
    else max:=y;
    end;
    begin
    readln(n);
    for i:=1 to n do
    readln(a[i]);
    for i:=1 to n do
    b[i]:=1;
    for i:=1 to n do
    for j:=i+1 to n do
    if copy(a[j],1,length(a[i]))=a[i] then b[j]:=max(b[j],b[i]+1);
    s:=0;
    for i:=1 to n do
    if b[i]>s then s:=b[i];
    write(s);
    end.

  • 0
    @ 2017-08-10 20:42:22

    数据有点水,随便写了一个就过了
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    using namespace std;
    int n;
    struct node
    {
    char data[76];

    };
    node s[2001];
    int f[2001];
    bool in_it(node a,node b)
    {
    if (strlen(a.data)>strlen(b.data)) return false;
    for (int k=0;k<=strlen(a.data)-1;k++)
    if (a.data[k]!=b.data[k])
    return false;
    return true;
    }
    int main()
    {

    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
    scanf("%s",s[i].data);
    }
    for (int i=1;i<=n;i++)
    f[i]=1;
    for (int i=1;i<=n;i++)
    for (int j=1;j<i;j++)
    if (in_it(s[j],s[i]))
    f[i]=max(f[i],f[j]+1);
    int maxn=f[1];
    for (int i=2;i<=n;i++)
    maxn=max(maxn,f[i]);
    printf("%d\n",maxn);
    return 0;
    }

  • 0
    @ 2017-05-12 15:21:16

    计算相邻单词最长的公共前缀长度,就可以一步步往后逆推,得到每两个单词公共前缀的长度。[]

    #include <cstdio>
    #include <cstring>
    
    
    int same(char *sa, char *sb)
    {
        int t = 0;
        for (; *(sa+t) != 0 && *(sb+t) != 0; t++)
        {
            if (sa[t] != sb[t]) return t;
        }
        return t;
    }
    
    int lens[2020][2];
    int dp[2020];
    char s[2020][80];
    
    int main()
    {
        int n;
        scanf("%d",&n);
        if (n == 1)
        {
            printf("%d\n",1);
            return 0;
        }
        scanf("%s",s[0]);
        lens[0][0] = 0; lens[0][1]= strlen(s[0]);
        dp[0] = 1;
        int ans = 1;
        for (int i = 1; i < n; i++)
        {
            scanf("%s",s[i]);
            int len = strlen(s[i]), head = same(s[i-1],s[i]);
            lens[i][0] = head;
            lens[i][1] = len - head;
            int j = i - 1;
            dp[i] = 1;
            while (j >= 0)
            {
                if (head == lens[j][0] + lens[j][1])
                {
                    dp[i] = dp[j] + 1;
                    break;
                } 
                if (lens[j][0] < head) head = lens[j][0];
                j--;
            }
            if (dp[i] > ans) ans = dp[i];
            
        }
        printf("%d\n",ans);
    } 
    
  • 0
    @ 2017-02-02 22:07:10

    trie树查找,为什么第一眼就是trie。。。

    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdlib>
    #include<vector>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
    if(x=='-')bj=-1;
    x=getchar();
    }
    while(x>='0'&&x<='9') {
    num=num*10+x-'0';
    x=getchar();
    }
    return num*bj;
    }
    const int maxn=300000;
    struct Tree {
    int child[65],bj;
    void clear() {
    memset(child,0,sizeof(child));
    bj=0;
    }
    };
    struct Trie {
    Tree tree[maxn];
    int cnt;
    void init() {
    cnt=0;
    memset(tree,0,sizeof(tree));
    }
    void insert(string s) { //插入字符串s
    int x=0;
    for(int i=0; i<s.length(); i++) {
    int y=s[i]-'a';
    if(tree[x].child[y]==0) { //没有此结点,新建结点
    tree[x].child[y]=++cnt;
    tree[cnt].clear();
    x=cnt;
    } else x=tree[x].child[y];
    }
    tree[x].bj=1;
    }
    int Find(string s) {
    int x=0,sum=0;
    for(int i=0; i<s.length(); i++) {
    int y=s[i]-'a';
    if(tree[x].child[y]==0)return -1; //不在树中
    x=tree[x].child[y];
    sum+=tree[x].bj;
    }
    return sum;
    }
    };
    Trie trie;
    int n,ans=0;
    string s[2005];
    int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++) {
    cin>>s[i];
    trie.insert(s[i]);
    }
    for(int i=1; i<=n; i++)ans=max(ans,trie.Find(s[i]));
    printf("%d\n",ans);
    return 0;
    }

    -------华丽的昏割线-------
    的确也可以用c++库函数LIS做,但是用的string速度要慢很多
    -------华丽的昏割线-------

    #include<algorithm>
    #include<iostream>
    #include<iomanip>
    #include<cstring>
    #include<cstdlib>
    #include<vector>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    using namespace std;
    inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
    if(x=='-')bj=-1;
    x=getchar();
    }
    while(x>='0'&&x<='9') {
    num=num*10+x-'0';
    x=getchar();
    }
    return num*bj;
    }
    int n,ans=0;
    string s[2005];
    int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++)cin>>s[i];
    for(int i=1; i<=n; i++) {
    int sum=0;
    for(int j=1; j<=i; j++)
    if(s[i].find(s[j])==0)sum++;
    ans=max(ans,sum);
    }
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2016-11-19 14:46:30

    最长上升子序列题目吧
    var
    a:array[1..2000] of string;
    l:array[1..2000] of integer;
    i,j,n,max:integer;
    function maxn(a,b:longint):longint;
    begin
    if a>b then exit(a) else exit(b);
    end;

    begin
    readln(n);
    for i:=1 to n do
    begin
    l[i]:=1;
    readln(a[i]);
    end;
    for i:=2 to n do
    for j:=1 to i-1 do
    if pos(a[j],a[i])=1 then
    l[i]:=maxn(l[i],l[j]+1);
    max:=0;
    for i:=1 to n do
    if l[i]>max then max:=l[i];
    writeln(l[i]);
    end.

  • 0
    @ 2016-11-09 20:05:58

    /最后一个点是猴子派来的吗
    #include <iostream>
    #include <string>

    using namespace std;

    #define MAXS 2001

    int n;
    string word[MAXS];
    int f[MAXS];

    int main()
    {
    int i,j;
    string te;
    int t;
    cin>>n;
    for(i=0;i<=n;++i)
    f[i]=1;
    for(i=1;i<=n;++i)
    cin>>word[i];
    //f[n]=1;
    for(i=n-1;i>0;--i)
    {
    t=word[i].size();
    for(j=n;j>i;--j)
    {
    if(word[i][0]!=word[j][0])continue;
    te=word[j].substr(0,t);
    if(te==word[i])
    f[i]=max(f[i],f[j]+1);
    }
    }
    j=-1;
    for(i=0;i<=n;++i)
    j=max(j,f[i]);
    cout<<j;
    return 0;
    }

  • 0
    @ 2016-11-04 20:09:56

    TRIE树dp什么乱七八糟的。。貌似是trie树上的最长单词链单词数。。。啊一次A。。Orz

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <map>
    #include <vector>
    #include <stack>
    #include <queue>

    using namespace std;

    int n,num=1;
    char in[1000];

    struct T{
    int tot,ch[300];
    }t[10000];

    int insert(char s,int &x){
    !x&&(x=++num);
    if(
    (s+1)=='\0')return t[x].tot=1;
    insert(s+1,t[x].ch[*(s+1)]);
    }

    int dfs(int x,int ret=0){
    for(register int i=0;i<300;i++)t[x].ch[i]&&(ret=max(ret,dfs(t[x].ch[i])));
    return ret+(t[x].tot==1);
    }

    int main(){
    scanf("%d",&n);
    for(register int i=1;i<=n;i++){
    scanf("%s",in);
    insert(in,t[1].ch[*in]);
    }

    printf("%d\n",dfs(1));
    }

  • 0
    @ 2016-11-02 09:05:36

    Tire树

    #include<bits/stdc++.h>
    using namespace std;
    
    const int alphabet_size=30;
    const int up=2000+5;
    int maxn=0;char chr[80];
    
    struct Trie
    {
        int ch[up][alphabet_size];bool val[up];
        int siz;
        Trie() { siz=1;memset(ch[0],0,sizeof(ch[0]));memset(val,0,sizeof(val)); }
        int idx(char c)  { return c-'a'; }
        void insert(char* s)
        {
            int u=0,n=strlen(s),v=1,c=0,cur=0;
            for(int i=0;i<n;i++)
            {
                c=idx(s[i]);
                if(val[u]) v++;
                if(!ch[u][c])
                {
                    memset(ch[siz],0,sizeof(ch[siz]));
                    ch[u][c]=siz++;
                }
                u=ch[u][c];
            }
            val[u]=1;
            if(maxn<v) maxn=v;
        }
    } stree;
    
    int main()
    {
        //freopen("stringline.in","r",stdin);
        //freopen("stringline.out","w",stdout);
        int n;
        
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%s",chr);
            stree.insert(chr);
        }
        printf("%d\n",maxn);
        return 0;
    }
    

信息

ID
1028
难度
4
分类
动态规划 | LIS 点击显示
标签
(无)
递交数
5973
已通过
2413
通过率
40%
被复制
4
上传者