没人用string自带的函数？？？
```
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#define N 2005
using namespace std;

int n,dp[N];
string s[N];

bool cmp(int x,int y){
return x>y;
}

int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>s[i];
dp[i]=1;
}
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(s[i].compare(0,s[j].size(),s[j])==0){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
sort(dp,dp+n,cmp);
cout<<dp[0];
return 0;
}
```

没人用string自带的函数？？？
```
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#define N 2005
using namespace std;

int n,dp[N];
string s[N];

bool cmp(int x,int y){
return x>y;
}

int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>s[i];
dp[i]=1;
}
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(s[i].compare(0,s[j].size(),s[j])==0){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
sort(dp,dp+n,cmp);
cout<<dp[0];
return 0;
}

数据规模才2000，建议是用库函数，做到一个是10000的题目，n方的超市，要用栈优化
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int n,ans=-1;
char a[10005][55];
int main()
{
int i,j,k;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%s",a[i]);
for(i=1;i<=n;i++)
{
int sum=0;
for(j=1;j<=i;j++)
{
if(strstr(a[i],a[j]))
sum++;
}
ans=max(ans,sum);
}
printf("%d\n",ans);
return 0;
}

DFS 记录ans
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

int n,f[2100]={0};
char a[2100][80];

int check(int i,int j){
//i包含于j
int flag=1;
for(int x=0;x<strlen(a[i]);x++)
if(a[i][x]!=a[j][x]){
flag=0;
break;
}
return flag;
}

int dfs(int u){
int ans=0;
for(int i=u+1;i<=n;i++){
if(!check(u,i))
break;
if(f[i]==0)
f[i]=dfs(i);
ans=std::max(ans,f[i]);
}

return ans+1;
}

int main(){
freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
std::cin>>a[i];
for(int i=1;i<=n-1;i++){
if(f[i]==0)
f[i]=dfs(i);
}

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

ans=binary_search＋LIC

trie树就好QAQ
```c++
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5;

int tri[maxn][27];
int top=1;
inline void ins(char *s){
int rt,nxt;
for(rt=0;*s;rt=nxt,++s){
nxt=tri[rt][*s-'a'];
if(!nxt)nxt=tri[rt][*s-'a']=top++;
}
tri[rt][26]++;
}

int ans,n;

inline void dfs(int x,int res){
for(int i=0;i<26;i++)
if(tri[x][i])dfs(tri[x][i],res+(tri[x][26]>0));
ans=max(ans,res+tri[x][26]);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
char s[100];
scanf("%s",s);
ins(s);
}
dfs(0,0);
cout<<ans;
return 0;
}
测试数据 #0: Accepted, time = 0 ms, mem = 21696 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 21696 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 21696 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 21696 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 21696 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 21700 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 21700 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 21696 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 21696 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 21696 KiB, score = 10
```

不要DP或者LIS
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
string word[2001];
int n,ans;
int f[2001];
bool work(int x,int y)
{
int l=word[x].size();
for(int i=0;i<l;i++)
{
if(word[x][i]!=word[y][i])return false;
}
return true;
}

int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
cin>>word[i];
for(int j=0;j<i;j++)
{
if(work(j,i))f[i]=max(f[i],f[j]);//表示包括某一个单词
}
f[i]++;
}
for(int i=0;i<n;i++)
ans=max(f[i],ans);
printf("%d",ans);
return 0;
}

题解+代码

//单调栈可AC
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
#define MAXN 2001
using namespace std;

int n,i,j;
int ans;
int si;
string word[MAXN];
stack <string> s;

int mymax(int a,int b)
{
    return a>b?a:b;
}

bool cmp (string a,string b)
{
    if (a.size()<=b.size()) return false;
    for (int i=0;i<b.size();i++)
    {
        if (a[i]!=b[i]) return false;
    }
    return true;
}

int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        cin>>word[i];
    for (i=1;i<=n;i++)
    {
        ans=mymax(ans,s.size());
        if (s.empty())
        {
            s.push(word[i]);
            continue;
        }
        if (cmp(word[i],s.top()))
        {
            s.push(word[i]);
            continue;
        }
        else
        {
            while (!s.empty())
            {
                s.pop();

                if (s.empty()||cmp(word[i],s.top()))
                {
                    s.push(word[i]);
                    break;
                }
            }
        }
        ans=mymax(ans,s.size());
    }
    ans=mymax(ans,s.size());
    printf("%d",ans);
    return 0;
}

type ty=string[80];
var n,i,j,l,h,mid,xmax:integer;
a:array[0..2001] of ty;
f:array[0..2001] of integer;
function max(aa,bb:integer):integer;
begin
if aa>bb then exit(aa);
exit(bb);
end;
function find(fs:ty):boolean;
begin
l:=1;
h:=i-1;
repeat
mid:=(l+h) div 2;
if a[mid]=fs then exit(true);
if a[mid]<fs then l:=mid+1
else h:=mid-1;
until l>h;
exit(false);
end;
begin
readln(n);
for i:=1 to n do
begin
readln(a[i]);
for j:=1 to length(a[i])-1 do
if find(copy(a[i],1,j)) then f[i]:=max(f[i],f[mid]);
inc(f[i]);
xmax:=max(xmax,f[i]);
end;
writeln(xmax);
end.
传统二分+动规

#include<stdlib.h>
#include<stdio.h>
#include <string.h>
main(){
char s[2000][75];
int len[2000];
int i,j,k,n,tmpn,max=1,fs;
scanf("%d",&n);
for(i=0;i<n;i++) {scanf("%s",s[i]);len[i]=strlen(s[i]);}
for(i=n-1;i>0;i--){
tmpn=1;fs=i;
for(j=i-1;j>=0;j--){
if(len[fs]<len[j]) continue;
for(k=0;k<=len[j];k++) if(s[fs][k]!=s[j][k])break;
if(k==len[j]) {tmpn++;fs=j;}
}
if(max<tmpn) max=tmpn;
}
printf("%d",max);
}

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int Max=2005;
string s[Max],b[Max];
int Search(string str,int l,int r)
{
int m;
while(l<=r)
{
m=(l+r)/2;
//cout<<l<<r<<m<<endl;
if(str.compare(0,b[m].size(),b[m])==0&&str>b[m])l=m+1;
else r=m-1;
}
return l;
}
int main()
{
ios::sync_with_stdio(0);
int n,mx=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i];
int len=1,pos;
b[1]=s[1];
for(int i=2;i<=n;i++)
{
if(s[i].compare(0,b[len].size(),b[len])==0)
{
len++;
b[len]=s[i];
}else
{
pos=Search(s[i],1,len);
b[pos]=s[i];
}
}
//for(int i=1;i<=len;i++)cout<<b[i]<<endl;
cout<<len;
return 0;
}

两个程序都是满分，但输入
7
asd
asdft
asdfghu
asdfty
asdftyu
asdfg
asdfgh
时出来的结果不一样，求问？

#include<stdio.h>//求问哪里错了
#include<stdlib.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include<vector>
using namespace std;
int i,j,n,lenb,lenc,flag,k,max1;
struct peo
{
char a[80];
int sum;
}pel[2004];
void pan(char b[80],char c[80])
{
flag=0;
lenb=strlen(b);
lenc=strlen(c);
if(lenb>lenc)
return ;
for(j=0;j<lenb;j++)
{
if(b[j]!=c[j])
{
flag=1;
break;
}
if(flag==0)
{
pel[k].sum=max(pel[k].sum,pel[i].sum+1);
}
}
return ;
}
int main()
{
cin>>n;
for(i=1;i<=n;i++)
{
cin>>pel[i].a;
pel[i].sum=0;
}
for(i=1;i<n;i++)
{
for(k=1;k<=n;k++)
{
if(i==k)
continue;
pan(pel[i].a,pel[k].a);
}
}
for(i=1;i<=n;i++)
{
if(pel[i].sum>max1)
max1=pel[i].sum;
}
cout<<max1+1<<endl;
return 0;
}

include <stdio.h>

char a[2002][78];
int maxlen[2002];

int main (void)
{
int n, i, j, k, flag, max;
scanf("%d",&n);
for (i=0; i<n; i++) {
scanf("%s",a[i]);
maxlen[i] = 1;
}
for (i=1, max=1; i<n; i++) {
for (j=0; j<i; j++) {
for (k=0, flag=1; a[j][k]!='\0'; k++) {
if (a[j][k] != a[i][k]) {
flag=0;
break;
}
}
if (flag && maxlen[i]<maxlen[j]+1)
maxlen[i] = maxlen[j]+1;
}
if (max < maxlen[i])
max = maxlen[i];
}
printf("%d\n",max);
return 0;
}
一遍编译过

uses math;
var n,i,j,len:integer;
  a:array[0..2000] of string;
  dp:array[0..2000] of integer;
begin
  readln(n);
  for i:=1 to n do readln(a[i]);
  len:=1;
  fillword(dp,sizeof(dp) div 2,1);
  for i:=1 to n do
    for j:=1 to n do
      if (i<>j) and (copy(a[i],1,length(a[j]))=a[j]) then begin
        dp[i]:=max(dp[j]+1,dp[i]);
        len:=max(dp[i],len);
      end;
  write(len);
end. 

典型的最长上升子序列
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;

const int maxn = 2010;
const int maxl = 80;

int n;
string words[maxn];
int f[maxn];

bool cmp (int x, int y) {
int l = words[x].size();
for (int i = 0; i < l; i++) {
if (words[x][i] != words[y][i]) return false;
}
return true;
}

int main ()
{
freopen ("in.txt", "r", stdin);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> words[i];
for (int j = 0; j < i; j++) {
if (cmp (j, i)) f[i] = max (f[i], f[j]);
}
f[i]++;
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (ans < f[i]) ans = f[i];
}
cout << ans;
return 0;
}
```

、、、c++
var
a:array[1..2000]of string;
b:array[1..2000]of integer;
i,j,max,n:integer;
begin
readln(n);
for i:=1 to n do readln(a[i]);
b[n]:=1;
for i:=n-1 downto 1 do
begin
max:=0;
for j:=i+1 to n do
if (pos(a[i],a[j])=1) and (a[i]<>a[j]) and (b[j]>max) then max:=b[j];
b[i]:=max+1;
end;
max:=0;
for i:=1 to n do
if b[i]>max then max:=b[i];
writeln(max);
end.
、、、

最长上升子序列nlogn
c++
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int Max=2005;
string s[Max],b[Max];
int Search(string str,int l,int r)
{
int m;
while(l<=r)
{
m=(l+r)/2;
//cout<<l<<r<<m<<endl;
if(str.compare(0,b[m].size(),b[m])==0&&str>b[m])l=m+1;
else r=m-1;
}
return l;
}
int main()
{
ios::sync_with_stdio(0);
int n,mx=0;
cin>>n;
for(int i=1;i<=n;i++)cin>>s[i];
int len=1,pos;
b[1]=s[1];
for(int i=2;i<=n;i++)
{
if(s[i].compare(0,b[len].size(),b[len])==0)
{
len++;
b[len]=s[i];
}else
{
pos=Search(s[i],1,len);
b[pos]=s[i];
}
}
//for(int i=1;i<=len;i++)cout<<b[i]<<endl;
cout<<len;
return 0;
}


注意是前缀不是包含!

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char a[2007][100];
int n, b[2007] = {0};
bool is(char *a, char *b)
{
int la = strlen(a);
// int lb = strlen(b);
int x = 0;
for(int i = 0; i < la; i++)
{
if(a[i] == b[i])
continue;
else {
x = 1;
break;
}
}
if(x == 0)
return true;
if(x == 1)
return false;
}
int dp(int k)
{
if(b[k] > 0)
return b[k];
for(int i = 1; i < k; i++)
if(is(a[i], a[k]))
b[k] = max(b[k], dp(i) + 1);
return b[k];
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
dp(i);
sort(b + 1, b + n + 1);
cout << b[n] + 1;
return 0;
}
刚学c++一学期，希望我的代码对初学者有用

/*************
*Author:chanjun
*email:15755396353@163.com
*************/

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

#define INF 0x3f3f3f3f
#define EXP 1e-8

#define LL long long

#define logic(a,b) (strstr((a),(b)) == (a))

char s[2001][75];

int main(){

//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
int n;
scanf("%d",&n);

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

}

int f[2001] = {0};
int ans = 1;

for (int i = 0; i < n; ++i){
for (int j = 0; j < i; ++j){
if (logic(s[i],s[j])){
f[i] = max(f[i],f[j]+1);
}
ans = max(ans,f[i]);
}
}

cout << ans+1 << endl;
//system("pause");
return 0;
}