夏天的飞鸟，飞到我的窗前唱歌，又飞去了。
秋天的黄叶，它们没有什么可唱，只叹息一声，飞落在那里。
有 n 个括号序列，你可以把它们排列之后首尾相连拼在一起，然后删去一些字符使得剩下的是合法括号序列。求最长的序列长度。
\(\sum|S|\leq5*10^6\)
首先我们注意到如果一个串中存在合法子序列（注意不是子串），那么这个串不管放在哪里这个子序列都是可以放进这个合法括号序列里面的。于是我们在输入这个串的时候就判断一下，这个串里面有没有合法的括号序列，如果有就直接加进去答案里，然后删掉这个序列，方便以后处理。
观察到删去合法子序列的串都是\()))))...)))(((((...(((\)的形式（不然早就自己匹配上了不是么）。
对于一个串\(i\)，我们设它有有\(a_i\)个\("("\)，有\(b_i\)个\(")"\)。
接下来我们要考虑如何贪心了。
我们肯定要将\(a_i>b_i\)的放在前面，\(a_i<b_i\)的放在后面。
那么对于所有\(a_i>b_i\)的，我们将\(a_i\)更大的放在前面，这样可以更多地和后面匹配。
同样对于所有\(a_i<b_i\)的，我们将\(b_i\)更大的放在后面，这样可以更多地和前面匹配。
就是这么简单。我代码能力真的是超级差，写个这个东西还错那么多次。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t, n, ans;
char ch[N];
struct node {
int q, h;
}a[N];
inline int zfx(int x) {
if(x<0) return -1;
if(x==0) return 0;
if(x>0) return 1;
}
bool operator <(node a, node b) {
if(zfx(a.q-a.h)!=zfx(b.q-b.h)) {
return zfx(a.q-a.h)>zfx(b.q-b.h);
}
if(zfx(a.q-a.h)<0) {
return a.q>b.q;
} else {
return a.h<b.h;
}
}
int main() {
scanf("%d", &t);
while(t--) {
ans=0;
scanf("%d", &n);
for(int i=1; i<=n; i++) {
a[i].q=a[i].h=0;
scanf("%s", &ch);
int tmp=strlen(ch);
for(int j=0; j<tmp; j++) {
if(ch[j]==‘(‘) {
a[i].q++;
}
if(ch[j]==‘)‘) {
if(a[i].q>0) a[i].q--, ans++;
else a[i].h++;
}
}
}
sort(a+1, a+n+1);
int yq=0;
for(int i=1; i<=n; i++) {
if(a[i].h&&yq) {
ans+=min(a[i].h, yq);
yq-=min(a[i].h, yq);
}
if(a[i].q) {
yq+=a[i].q;
}
}
printf("%d\n", ans*2);
}
}
打一个怪兽要先掉\(a_i\)滴血再补\(b_i\)滴血。树上除根节点以外每个点有个怪兽，你从根节点开始，打完一个点父亲才能打这个点，直到打完整颗树，问最少要多少血使得血始终非负。\(n ≤ 10^6\)
我一开始以为题目说要沿着树的链打下去的，那不就成了一道水逼DP了。。。
容易发现这道题的贪心策略是和上一道题是一样的！（迫真容易）
若我们不考虑父亲的限制，就让你随便打，你当然就要按照上一道题的形式贪心，可以用堆来维护。
对于打完会补血的点即\(b_i>a_i\)，我们肯定让他排前面。这些点中我们肯定希望我一开始遇到的\(a_i\)越小越好。
对于打完会扣血的点即\(b_i<a_i\)，我们肯定让他排后面。我肯定希望所有都结束之后剩下的\(HP\)最小也就必须是\(b_{last}\)，于是我们要最小化\(b_{last}\)，显而易见地就按照\(b\)的降序来排列。
（这两个严谨的证明暂时未推出来，推到一半卡住了，暂时感性理解吧）
然后我们加上父亲的限制。
首先对于堆顶的元素，如果他的父亲被打掉了，那我可以也必须立刻去打这个，这两个就变成了一组直接关系，我们可以把这个点合并到他的父亲。
很容易就想到合并的公式，我当是没想到我是脑子出了什么问题
我们可以用并查集的维护父子关系，最后等到所有点都合并到\(1\)号之后，输出\(a_1\)即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n, t;
struct node {
ll a, b;
int u, id;
}a[N];
bool operator >(node a, node b) {
if(a.a>=a.b&&b.a<b.b) return true;
if(b.a>=b.b&&a.a<a.b) return false;
if(a.a<a.b) return a.a>b.a;
else return a.b<b.b;
}
bool operator +=(node &a, node b) {
ll A, B;
A=max(a.a, a.a-a.b+b.a);
B=a.b-a.a+b.b-b.a+A;
a.a=A, a.b=B;
}
int head[N], fa[N], cnt;
bool del[N];
struct EDGE {
int y, nex;
}edge[N<<1];
inline void add(int x, int y) {
edge[++cnt].y=y;
edge[cnt].nex=head[x];
head[x]=cnt;
}
priority_queue<node, vector<node>, greater<node> >q;
void dfs(int x, int f) {
fa[x]=f;
for(int i=head[x]; i; i=edge[i].nex) {
int y=edge[i].y;
if(y!=f) {
dfs(y, x);
}
}
}
int find(int x) {
if(del[fa[x]]) return fa[x]=find(fa[x]);
else return fa[x];
}
int main() {
scanf("%d", &t);
while(t--) {
memset(del, 0, sizeof(del));
memset(head, 0, sizeof(head));
cnt=0;
scanf("%d", &n);
a[1].a=a[1].b=a[1].id=0;
for(int i=2; i<=n; i++) {
a[i].u=i, a[i].id=0;
scanf("%lld%lld", &a[i].a, &a[i].b);
q.push(a[i]);
}
for(int i=1; i<n; i++) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
dfs(1, 1);
int nid=0;
while(!q.empty()) {
node to=q.top();
q.pop();
if(a[to.u].id!=to.id) continue;
del[to.u]=true;
int f=find(to.u);
a[f]+=a[to.u];
if(f!=1) {
a[f].id=++nid;
q.push(a[f]);
}
}
printf("%lld\n", a[1].a);
}
}
XSY Dissertation6-贪心和DP专题——贪心（HDU6299 HDU6326）
原文：https://www.cnblogs.com/2017gdgzoi1164/p/14585141.html