dp简单题解

#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
typedef long long LL;
typedef pair<int, string > pi;
typedef pair<LL, LL> pl;
const int N = 3e5 + 20;
const int INF = 0x3f3f3f3f;
const LL INFLL =0x3f3f3f3f3f3f3f3f;
string a[N];//存储名字字母
map<int , pi > dp; // 定义dp数组，用map来存最长子序列和当前最长子序列所对应的字典序最小的字符串。
void so() {
		string s;
		cin >> s;
		string ss = "";
		int k = 0;
		for(int i = 0 ; i < (int)s.size() ; i++ ){
			if(s[i] >= 'A' && s[i] <= 'Z'){
				a[k++] = ss;
				ss = "";
			}
			ss +=s[i];
		}
		a[k] = ss;
        // 上面的的代码是用来分割字母。
		for(int i = 1 ; i <= k ; i++){
			dp[i] = {1 , a[i]}; //dp的初始化，以i结尾的名字的长度为1，名字的字符为a[i]   
			for(int j = 1 ; j < i ; j++ ){
				if(a[i] > a[j]){ //如果名字比a[j]大，说明是上升的序列
					if(dp[i].fi < dp[j].fi + 1){ // 判断当前上升序列有没有dp[i] 的大
						dp[i].fi = dp[j].fi + 1;
						dp[i].se = dp[j].se + a[i]; // 有的话就更新一下字符串和最长子序列大小
					}
					else if(dp[i].fi == dp[j].fi + 1){ //如果他们是相等的，那我们就需要判断一下，当前的dp[i]中的字符串字典序和dp[j] + a[i] 的字典序谁更小
					if(dp[i].se > dp[j].se + a[i]) dp[i].se = dp[j].se + a[i];  // 如果更更小，就更新一下。
					}
				}
				
			}
		}
		int ans = 0;
		for(auto i : dp) ans = max(ans , i.se.fi); // 求最长的子序列
		V<string> v;
		for(auto i : dp) if(i.se.fi == ans) v.pb(i.se.se); //如果有很多的最长的子序列，收集起来。
		sort(all0(v));// 排序，选出最小的字典序的字符串
		cout <<v[0];//输出最小字典序的字符串   
		
}
int main() {
    IOS
    int tt=1;
  //  cin >> tt;
    while (tt--)
    so();
}