玉溪网站建设,凡客诚品网址是多少,天华集团设计公司,建站类平台排行榜考虑枚举偷的珠宝的个数k#xff0c;且假设它们按照坐标大小排好了序#xff08;x坐标排一次#xff0c;y坐标排一次#xff09;。
那么可以将条件转化一下#xff0c;
在珠宝按x坐标排好序时#xff0c; x坐标大于等于aia_iai的最多取bib_ibi个可以转化为取的前k−…考虑枚举偷的珠宝的个数k且假设它们按照坐标大小排好了序x坐标排一次y坐标排一次。
那么可以将条件转化一下
在珠宝按x坐标排好序时 x坐标大于等于aia_iai的最多取bib_ibi个可以转化为取的前k−bik-b_ik−bi个珠宝的x坐标要小于aia_iai。 同理x坐标小于等于aia_iai的最多可以取bib_ibi个可以转化为取的后k−bik-b_ik−bi个珠宝的x坐标要大于aia_iai。
y坐标同理。
那么这样的话就可以计算出取的每个珠宝的x,y坐标取值范围。
接下来有两种处理方法。 法一 法二
/*妙把 对区间内物品选择个数的限制 转为 选择一定数量物品时对物品坐标范围的限制
达到优化建图的效果*/
#includeiostream
#includecstdio
#includecstring
#includequeue
using namespace std;
typedef long long ll;
const int N400;
const int M15000;
const int inf2147483647;
struct Edge{int u,v,f,nxt;ll w;
}edge[M1];
int head[N],cnt,s,t,inque[N],pre[N];ll dis[N];
queueint que;
int n,m;ll ans;
struct Jewelry{int x,y;ll val;
}p[85];
struct Quiery{char ch;int a,b;
}q[325];
void add(int u,int v,int f,ll w){edge[cnt].uu;edge[cnt].vv;edge[cnt].ww;edge[cnt].ff;edge[cnt].nxthead[u];head[u]cnt;edge[cnt].uv;edge[cnt].vu;edge[cnt].w-w;edge[cnt].f0;edge[cnt].nxthead[v];head[v]cnt;
}
bool spfa(){memset(dis,-63,sizeof(dis));memset(inque,0,sizeof(inque));memset(pre,-1,sizeof(pre));dis[s]0;que.push(s);inque[s]1;while(!que.empty()){int uque.front();que.pop();inque[u]0;for(int ihead[u];i!-1;iedge[i].nxt){int vedge[i].v;if(edge[i].f0dis[v]dis[u]edge[i].w){dis[v]dis[u]edge[i].w;pre[v]i;if(!inque[v]){que.push(v);inque[v]1;}}} }if(pre[t]-1) return 0;return 1;
}
ll EK(){int flow;ll ret0;while(spfa()){flowinf;int xpre[t];while(x!-1){flowmin(edge[x].f,flow);xpre[edge[x].u];}xpre[t];while(x!-1){edge[x].f-flow;edge[x^1].fflow;retflow*edge[x].w;xpre[edge[x].u];}}return ret;
}
int lx[85],rx[85],ly[85],ry[85];
void solve(int k){memset(head,-1,sizeof(head));cnt0;memset(lx1,0,k2),memset(ly1,0,k2),memset(rx1,0x7f,k2),memset(ry1,0x7f,k2);for(int i1;im;i){if(q[i].chL) lx[q[i].b1]max(lx[q[i].b1],q[i].a1);if(q[i].chRkq[i].b) rx[k-q[i].b]min(rx[k-q[i].b],q[i].a-1);if(q[i].chD) ly[q[i].b1]max(ly[q[i].b1],q[i].a1);if(q[i].chUkq[i].b) ry[k-q[i].b]min(ry[k-q[i].b],q[i].a-1);}for(int i2;ik;i) lx[i]max(lx[i],lx[i-1]),ly[i]max(ly[i],ly[i-1]);for(int ik-1;i;i--) rx[i]min(rx[i],rx[i1]),ry[i]min(ry[i],ry[i1]);s0;tknnk1;for(int i1;ik;i){add(s,i,1,0);for(int j1;jn;j){if(lx[i]p[j].xp[j].xrx[i]) add(i,kj,1,0);if(ly[i]p[j].yp[j].yry[i]) add(knj,knni,1,0);}add(knni,t,1,0);}for(int j1;jn;j) add(kj,knj,1,p[j].val);ansmax(ans,EK());
}
int main(){scanf(%d,n);for(int i1;in;i)scanf(%d%d%lld,p[i].x,p[i].y,p[i].val);scanf(%d,m);for(int i1;im;i)scanf(%s%d%d,q[i].ch,q[i].a,q[i].b);for(int k1;kn;k) solve(k);printf(%lld\n,ans);return 0;
}
