题意:
给你一个数n和一个字符矩阵,矩阵中S(i, j)表示ai + a(i+1) +...aj的正负号,要你还原a序列,其中a序列中每个数的绝对值不大于10.
解题思路:
把题目转化成已知各个前缀和的大小关系,求每个前缀和的值。s(i, j) 符号为正的话,表示a[i]+a[i+1] +.. a[j] > 0,即前缀和sum[j] - sum[i-1] > 0,即sum[j] > sum[i-1],知道了大小关系后要确定每个前缀和的值,因为题目要保证a序列每个数绝对值不大于10,所以令最大的数的值为10,然后逐个减一即可。
/* ********************************************** Author : JayYe Created Time: 2013/10/1 10:42:04 File Name : JayYe.cpp *********************************************** */ #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int maxn = 15; int du[maxn], mp[maxn][maxn], vis[maxn], ans[maxn], sum[maxn], n; char s[maxn*maxn]; void solve() { int tmp = 10, tot = 0, now = 10; while(tot < n+1) { memset(vis, 0, sizeof(vis)); // 找出度数为0的 for(int i = 0;i <= n; i++) if(!du[i]) { sum[i] = now; du[i] = -1; vis[i] = 1; tot++; } now--; for(int i = 0;i <= n; i++) if(vis[i]) { for(int j = 0;j <= n; j++) if(mp[i][j]) { du[j]--; } } } } // 初始化度数和大小关系 void init() { memset(du, 0, sizeof(du)); memset(mp, 0, sizeof(mp)); } int main() { int t; scanf("%d", &t); while(t--) { init(); scanf("%d%s", &n, s); int cur = 0; for(int i = 1;i <= n; i++) { for(int j = i;j <= n; j++) { char ch = s[cur++]; if(ch == '+') { mp[j][i-1] = 1; du[i-1]++; } else if(ch == '-') { mp[i-1][j] = 1; du[j]++; } } } solve(); for(int i = 1;i <= n; i++) ans[i] = sum[i] - sum[i-1]; for(int i = 1;i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' '); } return 0; }