本文主要是介绍UVA - 1423（拓扑排序），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目网址点击打开链接
；
妈耶真的是这个想法太奇妙；
以前拓扑排序不太懂。这里加几个关于拓扑排序的博客。有一篇代码虽然是java，但是思想是不错的点击打开链接
点击打开链接；
解题思路：
把题目转化成已知各个前缀和的大小关系，求每个前缀和的值。s(i, j) 符号为正的话，表示a[i]+a[i+1] +.. a[j] > 0，即前缀和sum[j] - sum[i-1] > 0，即sum[j] > sum[i-1]，知道了大小关系，把他的大小顺序看成是序列，因此是 sum[j] - >sum[i-1],所以对于i-1这一位入度要加，然后建立j - > i-a的路径；
处理完整个串之后就会建立一个偏序的图集；然后进行拓扑排序，因为题目要保证a序列每个数绝对值不大于10，所以令最大的数的值为10，然后逐个减一即可。
每一位的值可以通过sum【i】-sum【i-1】求得#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include<algorithm>
#include<vector>
#include<set>using namespace std;const int maxn=20+5;
int vis[maxn];
int inter[maxn];
int sum[maxn];
int mp[maxn][maxn];
string s;
int n;
int main()
{int T;cin>>T;while(T--){cin>>n;cin>>s;memset(vis,0,sizeof(vis));memset(inter,0,sizeof(inter));memset(sum,0,sizeof(sum));memset(mp,0,sizeof(mp));int cur=0;for(int i=1;i<=n;i++)for(int j=i;j<=n;j++){if(s[cur]=='+'){inter[i-1]++;mp[j][i-1]=1;}else if(s[cur]=='-'){inter[j]++;mp[i-1][j]=1;}cur++;}// for(int i=0;i<=n;i++)// cout<<inter[i]<<" ";// cout<<endl;int tot=0,now=10;while(tot<=n){for(int i=0;i<=n;i++)if(!inter[i]){vis[i]=1;inter[i]=-1;tot++;sum[i]=now;}now--;for(int i=0;i<=n;i++){if(vis[i]){for(int j=0;j<=n;j++)if(mp[i][j]){inter[j]--;}vis[i]=0;}}}for(int i=1;i<=n;i++){if(i!=1)cout<<" ";cout<<sum[i]-sum[i-1];}cout<<endl;}return 0;
}
还有一种更加直接的做法：
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include<algorithm>
#include<vector>
#include<set>using namespace std;
const int maxn=20;
const int maxd=1000+5;
int N,M,K;
int len,t,n,sum[maxn];
string s;
int main()
{scanf("%d",&t);while(t--){cin>>n;memset(sum,0,sizeof(sum));cin>>s;len=0;for(int i=1;i<=n;i++)for(int j=i;j<=n;j++){if(s[len]=='+') sum[i-1]--;else if(s[len]=='-') sum[j]--;len++;}for(int i=1;i<=n;i++){if(i!=1)cout<<" ";cout<<sum[i]-sum[i-1];}cout<<endl;}// cout<<res<<endl;return 0;
}
这篇关于UVA - 1423（拓扑排序）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
