把各个单词看作数字，如果单词A是单词B的前缀，那我们说A

直接DP

当pos(a[j],a[i])=1时 f[i]:=max{f[i],f[j]+1}(1

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

一次通过，太感动了！！！！！！！！

庆祝ing!!!!!!

最长子序列！！！！！

最长不下降子序列

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 20ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：20ms

这个数据才2K

直接DP

只有我是用TRIE树做的……

提交了10次才过，不知为什么？原来是懒得看题，注意要是前缀，所以POS是值必须等于1，我就是因为懒得看题才会有这样的提交率：39 / 181 题 ( 22% )

O(N^nlogn)=AC!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

O(n^2)=AC

超弱的DP，越发得不能理解这一系列的题

一次AC。最长不下降子序列模型。

最长不降序列！！！！！！！！！！！！！！

动规！！！

#include<string>
#include<iostream>
using namespace std;

int n;
int f[2005];
string a[2005];
int pre(int m){
int r = m + 1;
int k;
//int ret = 0;
while(m > 0){
if(a[m].size() <= a[r].size()){
for(k = 0; k < a[m].size(); ++k){
if(a[m][k] != a[r][k]){
break;
}
}
if(k == a[m].size()){
return f[m];
}
}
--m;
}
return 0;
}
int main()
{
//freopen("test.txt", "r", stdin);
cin>>n;
int i;
int m_a_x;
for(i = 1; i <= n; ++i){
cin>>a[i];
}
f[0] = 0;
f[1] = 1;
m_a_x = 1;
for(i = 2; i <= n; ++i){
f[i] = pre(i - 1) + 1;
if(m_a_x < f[i]){
m_a_x = f[i];
}
}
cout<<m_a_x;
return 0;
}

trie 字典树解法

#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#define maxn 2010
using namespace std;

int val[2010],tot[2010],ans;

struct trie{
    int sz,ch[maxn][27];
    trie(){ sz=1; memset(ch[0],0,sizeof ch[0]);}
    int idx(char c) {return c-'a';}
    void insert(char *s)
    {
        int u=0,tot=1,n=strlen(s);
        for (int i=0;i<n;i++)
        {
            int c=idx(s[i]);
            if(!ch[u][c])
            {
                memset(ch[sz],0,sizeof ch[sz]);
                val[sz]=0;
                ch[u][c]=sz++;
            }
            tot+=val[u];
            u=ch[u][c];
        }
        val[u]++;
        ans=max(ans,tot);
    }
}trie;

int main()
{
    int cas;
    char str[75];
    scanf("%d",&cas);
    for (int i=1;i<=cas;i++)
    {
        scanf("\n%s",str);
        trie.insert(str);
    }
    printf("%d",ans);
    return 0;
}

不是栈模拟一下就可以过了吗
```pascal
uses math;
var
a,s:array[0..100010] of string;
n,i,t,ans:longint;

function start(p,x:string):boolean;
begin
start:=copy(p,1,length(x))=x;
end;

begin
readln(n);
for i:=1 to n do readln(a[i]);
s[0]:='';t:=0;ans:=0;
for i:=1 to n do begin
while (t>0) and not start(a[i],s[t]) do dec(t);
inc(t);s[t]:=a[i];ans:=max(ans,t);
end;
write(ans);
end.
```

可怕
枚一枚就过了……
```pascal
program MosPassWord;
var i,j,n,max:longint;
s:array[1..2000] of string;
f:array[1..2000] of longint;

begin
readln(n);
for i:=1 to n do readln(s[i]);
for i:=1 to n do
for j:=1 to n do
if pos(s[i],s[j])=1
then inc(f[j]);
for i:=1 to n do
if f[i]>max then max:=f[i];
writeln(max);
end.

评测状态 Accepted
题目 P1028 魔族密码
递交时间 2016-07-16 16:28:21
代码语言 C++

消耗内存 744 KiB

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 740 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 744 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 740 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 740 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 740 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 740 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 740 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 736 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 740 KiB, score = 10

测试数据 #9: Accepted, time = 78 ms, mem = 740 KiB, score = 10

Accepted, time = 93 ms, mem = 744 KiB, score = 100
代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

//N个字符串， N <= 2000 字符串长度小于75。并且是按字典序排列好， 没有相同的。
//如果一个串是另一个串的前缀，那么就能构成相连的词汇。 问从中选出一些串。 能够成多长的词汇长度。
//思路： 一维背包
//最长上升子序列

const int V = 2000 + 50;

const int MaxN = 80 + 5; //字母数
const int mod = 1000000000 + 7;

int N, dp[V], ans; //dp[i] 表示第i串最多有的前缀数

char ch[V][MaxN];

bool f(int i, int j) {

int p;

if(strlen(ch[i]) <= strlen(ch[j]))

return false;

for(p = 0; ch[j][p]; p++)

if(ch[i][p] != ch[j][p])

break;

if(ch[j][p] != '\0')

return false;

return true;

}

int main() {

//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int i, j;

cin>>N;
for(i = 0; i < N; i++)

scanf("%s", ch[i]);

memset(dp, 0, sizeof(dp));

for(i = 1; i < N; i++)

for(j = i - 1; j >= 0; j--)

if(f(i, j))

dp[i] = max(dp[i], dp[j] + 1);

for(i = 0; i < N; i++)

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

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

}

lieo 顺推

俺是 逆推

一定注意必须是从第一个位置开始的词- -

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

Well Done！