本文主要是介绍UVALive 4255 Guess，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你半个矩阵 如果(i,j)的位置是'-' 则说明sum[i...j]<0 如果是'+' 说明sum>0 如果是'0' 说明sum=0 给出一种满足这个矩阵的序列 序列元素绝对值在10以内
思路：
很容易想到的是将sum[i...j]转化为sum[j]-sum[i-1] 即用前缀和来表示 那么题中的矩阵就可以转化成前缀和之间的大小比较 也就是说 我们可以通过将前缀和当成点 将大小关系作为边 求出满足题意的前缀和的拓扑序 那么只需要让拓扑序大的比小的大1 即可很容易的控制元素的绝对值
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 15int T,n;
int in[N],sum[N],vis[N],qu[N],maz[N][N];
char str[N*N];void topo()
{int i,j,k,s,f;for(i=0,k=0,f=10;i<=n;k=0,f--){for(j=0;j<=n;j++){if(!vis[j]&&!in[j]) qu[k++]=j;}i+=k;for(j=0,s=k;j<s;j++){sum[qu[j]]=f;vis[qu[j]]=1;for(k=0;k<=n;k++){if(!vis[k]&&maz[qu[j]][k]) in[k]--;}}}
}int main()
{int i,j,k;scanf("%d",&T);while(T--){scanf("%d%s",&n,str);memset(in,0,sizeof(in));memset(maz,0,sizeof(maz));memset(vis,0,sizeof(vis));for(i=1,k=0;i<=n;i++){for(j=i;j<=n;j++){if(str[k]=='+'){in[i-1]++;maz[j][i-1]=1;}else if(str[k]=='-'){in[j]++;maz[i-1][j]=1;}k++;}}topo();for(i=1;i<=n;i++) printf("%d%s",sum[i]-sum[i-1],(i==n)?"\n":" ");}return 0;
}
这篇关于UVALive 4255 Guess的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
