设这个序列的前缀和为Si(0 <= i <= n)，S0 = 0
每一个符号对应两个前缀和的大小关系，然后根据这个关系拓扑排序一下。
还要注意一下前缀和相等的情况，所以用一个并查集来查询。
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxn = 15; 5 int n; 6 int G[maxn][maxn]; 7 char s[100]; 8 int sum[maxn], a[maxn]; 9 10 int topo[maxn], c[maxn], t; 11 12 void dfs(int u) 13 { 14 c[u] = 1; 15 for(int v = 0; v <= n; v++) if(G[u][v] && !c[v]) dfs(v); 16 topo[--t] = u; 17 } 18 19 void toposort() 20 { 21 t = n + 1; 22 memset(c, 0, sizeof(c)); 23 for(int u = 0; u <= n; u++) if(!c[u]) dfs(u); 24 } 25 26 int p[maxn]; 27 int find(int x) 28 { return x == p[x] ? x : p[x] = find(p[x]); } 29 30 void link(int x, int y) 31 { 32 int px = find(x), py = find(y); 33 if(px != py) p[px] = py; 34 } 35 36 int main() 37 { 38 //freopen("in.txt", "r", stdin); 39 40 int T; scanf("%d", &T); 41 while(T--) 42 { 43 scanf("%d", &n); 44 scanf("%s", s); 45 46 for(int i = 0; i <= n; i++) p[i] = i; 47 48 memset(G, 0, sizeof(G)); 49 int p = 0; 50 for(int i = 1; i <= n; i++) 51 for(int j = i; j <= n; j++) 52 { 53 if(s[p] == '+') G[i-1][j]++; 54 if(s[p] == '-') G[j][i-1]++; 55 if(s[p] == '0') link(i-1, j); 56 p++; 57 } 58 toposort(); 59 for(p = 0; p <= n; p++) if(topo[p] == 0) break; 60 s[0] = 0; 61 62 for(int i = p + 1; i <= n; i++) 63 { 64 int s1 = topo[i], s2 = topo[i-1]; 65 if(find(s1) == find(s2)) sum[s1] = sum[s2]; //前缀和相等 66 else sum[s1] = sum[s2] + 1; 67 } 68 for(int i = p - 1; i >= 0; i--) 69 { 70 int s1 = topo[i], s2 = topo[i+1]; 71 if(find(s1) == find(s2)) sum[s1] = sum[s2]; 72 else sum[s1] = sum[s2] - 1; 73 } 74 for(int i = 1; i <= n; i++) 75 { 76 if(i > 1) printf(" "); 77 printf("%d", sum[i] - sum[i - 1]); 78 } 79 puts(""); 80 } 81 82 return 0; 83 }