题目描述
题目分析
这是一道用DP解决的最长上升子序列（LIS）问题。
时间复杂度为O(n^2)的解法：
定义为“以
为末尾的最长上升子序列长度”，状态转移方程为：
由于这种递推方法需要往回看字典序比自己小的名字，因此在本题中采用会超时。
时间复杂度为O(n*logn)的解法：
定义为“长度为
的上升子序列中末尾元素的最小值”（不存在的话字符串为十个Z以确保最大）
状态转移方程为：
由于对于每个，都要从0到i的dp数组更新一遍，因此时间复杂度仍然为O(n^2)。
但dp数组在这里的特点是有序递增，因此可以用二分查找优化算法。
使用该算法得到的结果子序列就是从第一个名字开始依次字典序最小的方案。
求出具体子序列：
要实现该动态规划的回溯很简单，定义一个前驱数组即可，该数组记录了
作为某条子序列末尾元素时上一个元素的下标。
我的代码
注意题目细节：游客可能重名，而子序列又要求前一个必须严格小于后一个，因此通过upper_bound()函数找到dp[i]时注意看dp[i-1]是否等于当前名字，若是则不更新dp[i]的值；而使用lower_bound()就不会出现此问题。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<stack>
using namespace std;
string s;
string name[1000002];
string dp[1000002];
int dp_2[1000002];
int pre[1000002];
int N;
void init(){for(int i=0;i<N;i++){dp[i]="zzzzzzzzzzz";pre[i]=0x3f3f3f3f;}
}
int split(string str){int n=0;name[n]+=str[0];for(int i=1;i<str.length();i++){if(str[i]<='Z'&&str[i]>='A') n++;name[n]+=str[i]; }return (n+1);
}
int main(void)
{cin>>s;N=split(s);init(); //Binary Searchfor(int i=0;i<N;i++){int pos = lower_bound(dp,dp+N,name[i])-dp;dp[pos]=name[i];dp_2[pos]=i;if(pos!=0) pre[i]=dp_2[pos-1];} //Ourput Answerint t=0;for(int i=0;i<N;i++){if(dp[i]=="zzzzzzzzzzz"){t=dp_2[i-1];break; }}stack<int> ans;ans.push(t);while(pre[t]!=0x3f3f3f3f){t=pre[t];ans.push(t);}while(ans.size()){cout<<name[ans.top()];ans.pop();}return 0;
}
思路扩展
这里为了求出最长子序列建立了前驱数组。但也可以建立一个ans[i]字符串数组，代表了长度为i+1的最小字典序子序列。状态转移方程如下：
每当dp[i]更新时，若i=0，ans[i]=name[i]；若i>0，ans[i]=ans[i-1]+name[i]。最终输出结果直接输出最大i对应的ans[i]即可。
