题意：
给定长度为n-1的字符串s，由大于号和小于号构成， 存在一个序列a，满足当s[i]=’<‘时，a[i]<a[i+1]，当s[i]=’>'时，a[i]>a[i+1]， 序列a中的每个数都是非负数，问序列a所有元素的和的最小值是多少。 输出这个最小值。
数据范围：2<=n<=5e5
解法：
如果a
[i
]>a
[i
+1],那么i对i
+1建立一条有向边
,显然这样建出的图一定是拓扑图
,
令出度为
0的点的权值为
0,然后向外扩展就行了
,正确性显然
.
因为要从出度为
0的点开始扩展
,所以要反向建图
.
另外可能出现一条链的情况
,这时候元素的权值是递增的
,权值和最大到n
*(n
+1)/2,需要开longlong
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
const int maxm
=5e5+5;
vector
<int>g
[maxm
];
char s
[maxm
];
int in
[maxm
];
int d
[maxm
];
int n
;
signed main(){
scanf("%s",s
+1);
n
=strlen(s
+1);
n
++;
for(int i
=1;i
<=n
-1;i
++){
if(s
[i
]=='>'){
g
[i
+1].push_back(i
);
in
[i
]++;
}else{
g
[i
].push_back(i
+1);
in
[i
+1]++;
}
}
queue
<int>q
;
for(int i
=1;i
<=n
;i
++){
if(in
[i
]==0){
q
.push(i
);
}
}
int ans
=0;
while(!q
.empty()){
int x
=q
.front();q
.pop();
ans
+=d
[x
];
for(int v
:g
[x
]){
if(in
[v
]){
in
[v
]--;
d
[v
]=max(d
[v
],d
[x
]+1);
if(!in
[v
]){
q
.push(v
);
}
}
}
}
cout
<<ans
<<endl
;
return 0;
}
