#1766 : 字符串问题
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
一开始小 Hi 有一个空的字符串 T ，现在他想进行最少次数的操作使得 T 变成 S，操作有以下两种：
1.任选一个字符，将它加到 T 的最后面
2.选择 T 的一个子序列，将它加到 T 的最后面
定义一个串 A 是串 B 的子序列当且仅当串 A 可以由串 B 删掉某些位置后得到。
输入
第一行一个小写字母字符串 S
1 ≤ |S| ≤ 105
输出
输出最少需要几次操作
样例输入
aabaaaabaa
样例输出
5 #include <iostream>#include<bits/stdc++.h>using namespace std;const int MX=100000+1000;char s[MX],cps[MX];vector<int> g[30];int n;int main(){ while(cin>>s) { for(int i=0;i<30;i++) g[i].clear(); int p=0,st=-1,i=0; int cnt=0; n=strlen(s); while(i<n) { vps云服务器 char ch=s[p]; int up=upper_bound (g[ch-‘a’].begin(), g[ch-‘a’].end(), st)-g[ch-‘a’].begin(); // cout<<up<<endl; if(up==g[ch-‘a’].size()) { cnt++; if(st==-1) { g[ s[p++]-‘a’].push_back(i); } st=-1; for(int j=i;j<p;j++) g[ s[j]-‘a’].push_back(j); i=p; } else { st=g[ch-‘a’][up]; p++; } } if(i!=p) cnt++; cout<<cnt<<endl; } return 0;}
?
23602421
