最长上升子序列 (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;
}

字符串的题当然用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;
}

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;
}

//简单的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;
}

#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;
}

/*
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;
}  
*/   

单调栈做法
```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;
}
```

#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;
}

#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;
}

#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;
}//俺也不知道你们为啥那么复杂

#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;
}

用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;
}

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.

数据有点水，随便写了一个就过了
#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;
}

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

#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);
} 

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;
}

最长上升子序列题目吧
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.

/最后一个点是猴子派来的吗
#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;
}

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));
}

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;
}