按白书的解法，区间和转前缀和，知道任意两个前缀和Si，Sj的相对大小关系，找出一组Si的解即可。大小关系转化成图，注意相等的两个Si。
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define MAXN 1200 using namespace std; int n; const int Size = 40; char str[MAXN]; int Sum[Size]; int mp[Size][Size]; int d[Size]; queue<int> q; int depth[Size]; void Toposort() { int low = -10; while(!q.empty()) q.pop(); for(int i = 0;i <= n;i++) { if(d[i] == 0) { q.push(i); depth[i] = low; } } while(!q.empty()) { int cur = q.front(); q.pop(); Sum[cur] = depth[cur]; low++; for(int i = 0;i <= n;i++) { if(i == cur) continue; if(mp[cur][i] != 0) { mp[cur][i]--; d[i]--; if(d[i] == 0) { q.push(i); depth[i] = low; } } } } for(int i = 1;i <= n;i++) { printf("%d%s",Sum[i]-Sum[i-1],i==n?"":" "); } printf("\n"); } int main() { int T; scanf("%d",&T); while(T--) { memset(depth,0,sizeof(depth)); memset(Sum,0,sizeof(Sum)); memset(mp,0,sizeof(mp)); memset(d,0,sizeof(d)); scanf("%d",&n); scanf("%s",str); int t = n; int pos = 0; for(int i = 1;i <= n;i++) for(int j = i;j <= n;j++) { char ch = str[pos++]; if(ch == '+') { mp[i-1][j]++; d[j]++; } else if(ch == '-'){ mp[j][i-1]++; d[i-1]++; } } Toposort(); } return 0; }
