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

1103 - 萌萌哒的第八题

Time Limit：7s Memory Limit：128MByte

Submissions：143Solved：46

DESCRipTION

给出两个数列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)。求问最后最多能拿多少分。

INPUT 包含多组测试数据(<=5)，每组数据：第一行包含两个整数n(1 <= n <= 1000000), m(1 <= m <= 3000000) 接下来m行，每行两个整数(c, d)表示A(c)可以跟B(d)匹配。接下来两行，每行n个整数，分别表示A数列和B数列 OUTPUT 每组测试数据输出一行一个证书表示最大得分。 SAMPLE INPUT 4 4 1 2 2 1 3 4 3 3 4 4 5 1 2 3 5 6 SAMPLE OUTPUT 18

思路：

这个题同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+1
int 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);
    }
}

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

相关推荐