新网站建设公司,坑梓网站建设价格,德清网站建设,商城系统下载题目
长为n(n500)的尚未确定的括号串#xff0c;m(m500)个限制条件
第i个限制条件形如区间[li,ri]#xff0c;保证区间长度为偶数#xff0c;
定下来括号串#xff0c;满足最多的限制数#xff0c;使得每个限制对应的区间是一个合法的括号串
输出能满足的最多…题目
长为n(n500)的尚未确定的括号串m(m500)个限制条件
第i个限制条件形如区间[li,ri]保证区间长度为偶数
定下来括号串满足最多的限制数使得每个限制对应的区间是一个合法的括号串
输出能满足的最多的限制数
思路来源
官方题解
题解
不合法的情况
li和lj奇偶性不同liljrirj
考虑把(看成1)看成-1x[i]为括号串的前缀和数组
出现这种情况时要求x[li-1]x[lj-1]x[ri]且x[li-1]x[ri]
有x[lj-1]x[li-1]与奇偶性相同矛盾
所以出现一种冲突时就将这两个限制条件连一条边表示不能同时取 剩下的一定可以取构造方法
需要取的位置如果存在要取的li就放左括号如果存在要取的ri就放右括号
否则如果上一个字符是左括号则当前是右括号上一个字符是右括号则当前是左括号
即贪心把剩下的位置的前缀和降得尽可能低即可构造出
也可以考虑先把l都为奇数的放入再放入l为偶数的
因为任意两个都不严格相交只会存在内部包含的情况所以没有冲突 连边之后二分图最大独立集m-二分图最大匹配
跑dinic即可复杂度O(m^2.5)
代码
#includeiostream
#includecstdio
#includecstring
#includequeue
#includemap
using namespace std;
typedef long long ll;
const int INF0x3f3f3f3f;
const int maxn505;
const int maxm8*maxn*maxn;
int level[maxn];
int head[maxn],cnt;
int t,n,m,l[maxn],r[maxn];
int ss,ee;
struct edge{int v,nex;ll w;}e[maxm];
void init()
{cnt0;memset(head,-1,sizeof head);
}
void add(int u,int v,ll w)
{e[cnt].vv;e[cnt].ww;e[cnt].nexhead[u];head[u]cnt;
}
void add2(int u,int v,ll w,bool op)//是否为有向图
{add(u,v,w);add(v,u,op?0:w);
}
bool bfs(int s,int t)
{queueintq;memset(level,0,sizeof level);level[s]1;q.push(s);while(!q.empty()){int xq.front();q.pop();if(xt)return 1;for(int uhead[x];~u;ue[u].nex){int ve[u].v;ll we[u].w;if(!level[v]w){level[v]level[x]1;q.push(v);}}}return 0;
}
ll dfs(int u,ll maxf,int t)
{if(ut)return maxf;ll ret0;for(int ihead[u];~i;ie[i].nex){int ve[i].v;ll we[i].w;if(level[u]1level[v]w){ll MINmin(maxf-ret,w);wdfs(v,MIN,t);e[i].w-w;e[i^1].ww;retw;if(retmaxf)break;}}if(!ret)level[u]-1;//优化,防止重搜,说明u这一路不可能有流量了 return ret;
}
ll Dinic(int s,int t)
{ll ans0;while(bfs(s,t))ansdfs(s,INF,t);return ans;
}
int main(){ init();scanf(%d%d,n,m);ssm1,eem2;for(int j1;jm;j){scanf(%d%d,l[j],r[j]);if(l[j]1)add2(ss,j,1,1);else add2(j,ee,1,1);}for(int j1;jm;j){for(int k1;km;k){int xl[j]1,yl[k]1;if(x!y l[j]l[k] l[k]r[j] r[j]r[k]){if(x)add2(j,k,INF,1);else add2(k,j,INF,1);}}}printf(%lld\n,m-Dinic(ss,ee));return 0;
}
