题意：给定一串数字a1,a2....an，给出sij的正负数值。sij代表ai+...aj的大小。求一组结果满足此条件。-10<=ai<=10.
思路：
设：Bi = a1+ a2 + ... ai，则，我们可以求出Bj和Bi-1的大小关系。可以由大到小连一条有向边，对此有向图做拓扑排序。
拓扑排序的做法如下：我们规定节点初始值：Bk =0（这只是一个相对值，事实上我们求的ai是Bi与Bi-1的差值，所以Bi初始是什么都没有关系，我们求得是相对差）.
如果Bi 向Bj有一条有向边，那么Bi>Bj,说明Bi至少比Bj大1，我们用v[k]记录Bk的值，不断调整此数值。最终就能求得一组解。
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <iostream> using namespace std; #define Maxn 20
vector<int> g[Maxn];
int indeg[Maxn],v[Maxn];
int n; void init()
{
for(int i=0;i<Maxn;i++)
{
g[i].clear();
indeg[i] = 0;
v[i] = 0;
}
} void toposort()
{
queue<int> q;
for(int i=0;i<=n;i++)
{
if(indeg[i] == 0) q.push(i);
}
while(!q.empty())
{
int s = q.front();
q.pop();
for(int i=0;i<g[s].size();i++)
{
int t = g[s][i];
v[t] = min(v[t],v[s]-1);
if(--indeg[t] == 0)
{
q.push(t);
}
}
}
}
void output()
{
for(int i=1;i<=n;i++)
{
if(i!=n) printf("%d ",v[i]-v[i-1]);
else printf("%d\n",v[i]-v[i-1]);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int t;
char str[20];
scanf(" %d",&t);
while(t--)
{
init();
scanf(" %d",&n);
scanf("%s",str);
for(int i=1,p=0;i<=n;i++)
{
for(int j=i;j<=n;j++,p++)
{
if(str[p] == '-')
{
g[i-1].push_back(j);
indeg[j]++;
}
else if(str[p] == '+')
{
g[j].push_back(i-1);
indeg[i-1]++;
}
}
}
toposort();
output();
}
return 0;
}