nowcoder16450 托米的简单表示法

题目链接

思路

仔细理解一下题意可以发现。

对于每个完整的括号序列都是独立的，然后就想到分治。高度是序列中所有括号序列的最大值，宽度是所有括号序列宽度和\(+1\)。

然后仔细想了一下，这种分治应该是可以被卡成\(n^2\)的。

题解就比较厉害了。

其实基本思想和分治相似。

建立一棵树的模型。每到一个左括号就给当前节点添加一个子节点。每到一个右括号，就回到父亲节点。

等到建完这张图，发现其实就是把分治的过程给提前处理出来了。

然后对于这棵树\(dp\)一下就好了。

当前节点的高度是孩子中最大高度\(+1\)，宽度是孩子宽度之和\(+1\)，答案就是宽度\(\times\)高度\(-\)孩子的答案之和

代码

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cstring>

#include<bitset>

#include<vector>

using namespace std;

typedef long long ll;

#define int ll

const int N = 500000 + 100;

vector<int>e[N];

ll read() {

	ll x=0,f=1;char c=getchar();

	while(c<'0'||c>'9') {

		if(c=='-') f=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9') {

		x=x*10+c-'0';

		c=getchar();

	}

	return x*f;

}

char s[N];

int w[N],h[N];

int dfs(int u) {

	int k = e[u].size();

	w[u] = 1;

	h[u] = 0;

	int sum = 0;

	for(int i = 0;i < k;++i) {

		int v = e[u][i];

		sum += dfs(v);

		w[u] += w[v] + 1;

		h[u] = max(h[u],h[v]);

	}

	h[u]++;

	return !u ? sum : w[u] * h[u] - sum;

}

int fa[N];

signed main() {

	int T = read();

	while(T--) {

		scanf("%s",s + 1);

		int now = 0,tot = 0;

		memset(fa,0,sizeof(fa));

		int n = strlen(s + 1);

		for(int i = 1;i <= n;++i) {

			if(s[i] == '(') e[now].push_back(++tot),fa[tot] = now,now = tot;

			else now = fa[now];

		}

		printf("%lld\n",dfs(0));

		for(int i = 0;i <= tot;++i) e[i].clear();

	}

	return 0;

}