问题 D: 学 DP 导致的

目描述

DP 的一个经典应用便是求最长上升子序列。本题中，子序列指的是删除若干个字符（可以是 0 个或全部删除）后，保持其他字符的原有顺序得到的新字符串。
给出一个小写字母构成的字符串 S，将 S 拼接 k 次后会得到一个新字符串 S'。
求 S' 最长的子序列长度，使得子序列中字符的 ASCII 码严格递增。

输入

本题有多组数据。 输入的第一行有一个正整数 T（1≤T≤20），表示数据组数。
对于每组数据，输入一行，包括一个字符串 S(1≤∣S∣≤100) 和一个正整数 k(1≤k≤10100)，含义同题目描述。

输出

对于每组数据，输出一行一个正整数，表示答案。

样例输入 Copy

1
yummy 2

样例输出 Copy

3

提示

【样例解释】
S' 为 yummyyummy，最长的符合题意的子序列为 muy。

学DP导致的

字符串怎么比大小给我忘记了，寄 

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){string s,k,a="";cin>>s>>k;if(k.length()>2||(k.length()==2&&k>="26")){int c[30]{0},ans=0;for(auto i:s)c[i-'a']=1;for(int i=0;i<26;++i){if(c[i])ans++;}cout<<ans<<'\n';return;}int n=stoi(k),c[10009],l=0;for(int i=0;i<n;++i)a+=s;for(int i=0;i<a.length();++i){if(l==0)c[l++]=a[i]-'a';else{int f=-1;for(int j=l-1;j>=0;--j){if(c[j]>=(a[i]-'a'))f=j;}if(f==-1)c[l++]=a[i]-'a';else c[f]=a[i]-'a';}//for(int i=0;i<l;++i){cout<<char(c[i]+'a');}cout<<'\n';}//for(int i=0;i<l;++i){cout<<char(c[i]+'a');}cout<<l<<'\n';return;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}