题目地址：https://www.luogu.org/problem/show?pid=1481
这题于矩形嵌套问题类似，如果某个单词时是令一个单词的前缀，那么就是说a到b有一条有向边，那么就转化成为了DAG上的动态规划。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=2000+5; char s[MAXN][76]; int n,ans,f[MAXN]; int main() { int i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s",s[i]); } f[1]=1; for(i=2;i<=n;i++) { int maxx=0; for(j=i-1;j>=1;j--) { int l=strlen(s[j]); if(maxx<f[j]&&!strncmp(s[i],s[j],l)) maxx=f[j]; } f[i]=maxx+1; } for(i=1;i<=n;i++) ans=max(ans,f[i]); printf("%d\n",ans); return 0; } 吃惊的是这题也可以用栈来做（就与codevs1051一样了，甚至不需要排序），不过要慢一些。 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cstring> #include<algorithm> using namespace std; int n; string s[1000001]; string a[1000001]; int k=0; int top=0; bool pd(string x,string y) { if(x==y) return 0; int l=x.size(); if(x!=y.substr(0,l)) return 0; return 1; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>s[i]; sort(s+1,s+n+1); for(int i=1;i<=n;i++) { if(top==0) {top++; a[top]=s[i];} else while(top>0) { if(pd(a[top],s[i])==1) { top++; a[top]=s[i]; break; } else top--; } if(top==0) { top++; a[top]=s[i]; } k=max(k,top); } cout<<k<<endl; return 0; }
