题目描述：

给你一个字符串s，长度为n（n<= 50)，这个字符串对应着一个长度为n+1的数列ans，字符串和数列下标均从0开始。

字符串只有2种字符：

如果s[i] = D，表示ans[i] > ans[i+1]

如果s[i] = I, 表示ans[i] < ans[i+1]

求这个数列的最小字典序。

例子：

"IIIII"
Returns: {1, 2, 3, 4, 5, 6 }

"DI"
Returns: {2, 1, 3 }
"IIIID"
Returns: {1, 2, 3, 4, 6, 5 }
"DIIDID"
Returns: {2, 1, 3, 5, 4, 7, 6 }

解题报告：

方法一，自己想的，代码长：

首先，通过相邻两个数字的大小关系，利用floyd原理，可以得到尽可能多的两两之间的大小关系。

然后构有向图：i到j有一条边，说明ans[i]<ans[j]，利用top排序的方法，把他们排序，注意，当有同时有多个入度为0的节点时，没有大小的关系的两个节点之间，编号小的考前，这样便满足的字典序。

拍完序后，一次从小到大编号即可，代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int g[100][100];
struct node
{
    int id;
    node(int x){id = x;}
    friend bool operator < (const node a, const node b)
    {
        if (g[a.id][b.id] == 1) return 0;
        else if (g[b.id][a.id] == 1) return 1;
        return a.id > b.id;
    }
};
class PermutationSignature {
public:

int n;
int rd[100], que[1000];
bool vst[100];
vector <int> reconstruct(string s)
{
    n = s.length() + 1;
    memset(g, 0, sizeof(g));
    memset(rd, 0, sizeof(rd));
    memset(vst, 0, sizeof(vst));
    for(int i = 0; i < s.length(); i++)
        if (s[i] == 'I')
            g[i][i + 1] = 1;
        else
            g[i + 1][i] = 1;
    vector<int> ans;
    for(int i = 0; i < n; i++) ans.push_back(i);
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if (g[i][k] == 1 && g[k][j] == 1) g[i][j] = 1;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if (g[i][j] == 1) rd[j]++;
    priority_queue<node> jeo;
    for(int i = 0; i < n; i++)
        if (rd[i] == 0)
        {
            jeo.push(node(i));
            vst[i] = 1;
        }
    int cnt = 1;
    while(!jeo.empty())
    {
        int id = jeo.top().id; jeo.pop();
        ans[id] = cnt++;
        for(int i = 0; i < n; i++)
            if (g[id][i] == 1 && !vst[i])
                if (--rd[i] == 0)
                {
                    jeo.push(i);
                    vst[i] = 1;
                }
    }

    return ans;
}
};

方法二：看别人的，很巧妙：

假定答案序列暂为1~n+1， 这样，就满足了所有s[i] = I的部分，但是对于s[i] = D的部分还不满足，需要修改，由于需要字典序最小，所以只需把那一串连续的D的序列翻转即可达到要求。代码如下：

vector <int> reconstruct(string s)
{
    vetcot<int> ans;
    int n = s.length();
    for(int i = 1; i <= n + 1; i++) ans.push_back(i);
    for(int i = 0; i < n; i++)
        if (s[i] == 'D')
            for(int j = i; j >= 0 && s[j] == 'D'; j--)
                swap(ans[j], ans[j + 1]);
    return ans;
}