【动态规划|P1481 魔族密码】题目地址：https://www.luogu.org/problem/show?pid=1481
这题于矩形嵌套问题类似，如果某个单词时是令一个单词的前缀，那么就是说a到b有一条有向边，那么就转化成为了DAG上的动态规划。
#include
#include
#include
#include
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 吃惊的是这题也可以用栈来做（就与codevs1051一样了，甚至不需要排序），不过要慢一些。
#include
#include
#include
#include
#include
#include
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< 推荐阅读
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 数据结构与算法|【算法】力扣第 266场周赛
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- Android|关闭activity之前的所有activity，好方法
- 动态规划|动态规划 —— 状压DP (附一些位运算小知识)
- 区间DP —— 能量项链
- 动态规划 —— 区间DP
- Codeforces|Codeforces Round #605 (Div. 3) D. Remove One Element
- LeetCode-28 实现strStr() KMP算法