RQNOJ 429 词链：单调栈

题目链接：https://www.rqnoj.cn/problem/429

题意：

　　如果一张由一个词或多个词组成的表中，每个单词（除了最后一个）都是排在它后面的单词的前缀，则称此表为一个词链。

　　如：i,int,integer.

　　给你一堆按字典序排好的字符串，问你最长的词链有多长（词链中的字符串个数）。

题解：

　　单调栈。

　　找出单调性：

　　　　对于栈内的元素，从栈底到栈顶为单调，形成一个词链。

　　找出答案：

　　　　扫一遍给出的字符串，栈的最大高度即为答案。

　　维护单调性：

　　　　因为字符串按字典序排好，已经达到了是单调性最优的状态（贪心证明），所以就不用管扫描顺序了。

　　　　对于一个新扫到的字符串s[i]：

　　　　　　（1）如果满足单调性，则入栈。

　　　　　　　　即：1. 当前栈顶为s[i]的前缀(is_prefix(stk.top(),s[i]))。

　　　　　　　　　　2. 当前栈为空。

　　　　　　（2）如果不满足单调性，则弹出栈顶，直到满足单调性为止。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <stack>

 #define MAX_N 10005

 using namespace std;

 int n;

 int ans;

 string s[MAX_N];

 stack<string> stk;

 void read()

 {

     cin>>n;

     for(int i=;i<n;i++)

     {

         cin>>s[i];

     }

 }

 bool is_prefix(string sub,string dst)

 {

     if(sub.size()>dst.size()) return false;

     for(int i=;i<sub.size();i++)

     {

         if(sub[i]!=dst[i]) return false;

     }

     return true;

 }

 void solve()

 {

     ans=;

     for(int i=;i<n;i++)

     {

         while(!stk.empty() && !is_prefix(stk.top(),s[i]))

         {

             stk.pop();

         }

         stk.push(s[i]);

         ans=max(ans,(int)stk.size());

     }

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

RQNOJ 429 词链：单调栈

最新文章

热门文章