玲珑学院OJ 1103 萌萌哒的第八题【dp+线段树】

Time Limit：7s Memory Limit：128MByte

Submissions：143Solved：46

给出两个数列A和B，长度都为n，分别编号都是从1到n，再给出m个数对(c, d)，表示A数列的地c个数可以跟B数列的第d个数匹配，当这两个数被匹配上了，那么总分加上这两个数，但是每个数最多被匹配一次，而且匹配不能相交。也就是说，假设A(i)和B(j)匹配了，那么不能存在一个匹配A(u)和B(v)满足(u < i and v > j) or (u > i and v < j)。求问最后最多能拿多少分。

思路：

这个题同B题啊，一毛一样啊，只不过状态转移方程稍微差一丢丢啊..

设定dp【i】表示b数组最远匹配到a数组最远位子为i的最大匹配值。

那么有：dp【v】=max（dp【1~v-1】）+a【v】+b【i】；

这里线段树维护一下最大值即可。

时间复杂度O（nlogn）；

Ac代码：

#include<stdio.h>#include<string.h>#include<vector>using namespace std;#define lson l,m,rt*2#define rson m+1,r,rt*2+1int tree[1000050*8];int a[1000005];int b[1000005];int dp[1080500];vector<int >mp[1000005];void pushup(int rt){    tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);}int Query(int L,int R,int l,int r,int rt){    if(L<=l&&r<=R)    {        return tree[rt];    }    else    {        int m=(l+r)>>1;        int ans=0;        if(L<=m)        {            ans=max(Query(L,R,lson),ans);        }        if(m<R)        {            ans=max(Query(L,R,rson),ans);        }        return ans;    }}void build( int l ,int r , int rt ){    if( l == r )    {        tree[rt]=0;        return ;    }    else    {        int m = (l+r)>>1 ;        build(lson) ;        build(rson) ;        pushup(rt) ;    }}void update(int p,int c,int l,int r,int rt)//p阵营c数据.{    if(l==r)    {        tree[rt]=max(tree[rt],c);    }    else    {        int m=(l+r)>>1;        if(p<=m) update(p,c,lson);        else  update(p,c,rson);        pushup(rt);    }}inline void read(int &t) {    int f = 1;char c;    while (c = getchar(), c < '0' || c > '9') if (c == '-') f = -1;    t = c   -'0';    while (c = getchar(), c >= '0' && c <= '9') t = t * 10 + c  - '0';    t *= f;}int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        for(int i=1;i<=n;i++)mp[i].clear();        for(int i=0;i<m;i++)        {            int x,y;            read(x),read(y);            mp[y].push_back(x);        }        build(1,n,1);        for(int i=1;i<=n;i++)scanf("%d",&a[i]);        for(int i=1;i<=n;i++)scanf("%d",&b[i]);        for(int i=1;i<=n;i++)dp[i]=0;        for(int i=1;i<=n;i++)        {            int size=mp[i].size();            for(int j=0;j<size;j++)            {                int v=mp[i][j];                if(v==1)                {                    dp[v]=max(b[i]+a[v],dp[v]);                }                else                dp[v]=max(Query(1,v-1,1,n,1)+b[i]+a[v],dp[v]);            }            for(int j=0;j<size;j++)            {                int v=mp[i][j];                update(v,dp[v],1,n,1);            }        }        int ans=0;        for(int i=1;i<=n;i++)ans=max(ans,dp[i]);        PRintf("%d/n",ans);    }}