【题意】给定长度为n(<=2*10^5)的字符串，求最短的字典序最小的非子序列字符串。
http://arc081.contest.atcoder.jp/tasks/arc081_c
【算法】字符串DP
【题解】
先考虑计算最短长度，再考虑求字典序最小。
关键在于发掘出【最短的非子序列字符串】具有最优子结构，定义f(s)为字符串s的最短的非子序列字符串长度，假设最短的非子序列字符串为t，当t的第一个字母是c（任意字母）时，只有两种情况：
①s中无c，f(s)=1最短。
②对于s中最左边位置p的c，f(s)=f(s.suffix(p+1))+1，最后这个+1就是c。
很熟悉对吗？①是终止条件，②是状态转移，满足最优子结构性质，当确定第一个字母后，剩余部分可以转化为计算完毕的子问题。
那么正式定义状态转移方程，令f[i]表示字符串的后缀i的最短非子序列字符串的长度，pos[i][j]表示从位置i开始第一个字母j出现的位置。
状态转移方程：f[i]=min(f[pos[i][j]+1])+1，0<=j<26。
最后要求字典序最小，从f[0]开始对于每一步找到最小的字母c满足f[i]==f[pos[i][c]]+1输出即可。
复杂度O(n*26)。
考虑清楚边界问题！
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int f[maxn],pos[maxn][],n;
char s[maxn];
int main(){
scanf("%s",s);
n=strlen(s);
for(int i=;i<;i++)pos[n][i]=n;
f[n]=;f[n+]=;//即使没有后缀仍然需要长度为1，f[n]=1；如果没有相同字符的话就f[n+1]+1，所以f[n+1]=0。
for(int i=n-;i>=;i--){
for(int j=;j<;j++)pos[i][j]=pos[i+][j];
pos[i][s[i]-'a']=i;
f[i]=n+;
for(int j=;j<;j++)f[i]=min(f[i],f[pos[i][j]+]+);
}
int T=f[],p=;
while(T--){
for(int j=;j<;j++)if(f[pos[p][j]+]+==f[p]){
putchar('a'+j);
p=pos[p][j]+;
break;
}
}
return ;
}