0x58 数据结构优化DP

补写一下

poj3171 设f[i]表示覆盖L~i的最小花费，把区间按左端点排序，枚举区间，f[a[i].r]=min{f[a[i].l~(a[top].r-1)]}+a[i].c (当然还要和原值比较的)

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

struct node{int l,r,d;}a[];

bool cmp(node n1,node n2){return n1.r<n2.r;}

struct trnode

{

    int l,r,lc,rc,c;

}tr[];int trlen;

void bt(int l,int r)

{

    int now=++trlen;

    tr[now].l=l;tr[now].r=r;tr[now].c=(<<);

    tr[now].lc=tr[now].rc=-;

    if(l<r)

    {

        int mid=(l+r)/;

        tr[now].lc=trlen+;bt(l,mid);

        tr[now].rc=trlen+;bt(mid+,r);

    }

}

void change(int now,int p,int k)

{

    if(tr[now].l==tr[now].r){tr[now].c=k;return ;}

    int lc=tr[now].lc,rc=tr[now].rc;

    int mid=(tr[now].l+tr[now].r)/;

    if(p<=mid)change(lc,p,k);

    else      change(rc,p,k);

    tr[now].c=min(tr[lc].c,tr[rc].c);

}

int getmin(int now,int l,int r)

{

    if(tr[now].l==l&&tr[now].r==r)return tr[now].c;

    int lc=tr[now].lc,rc=tr[now].rc;

    int mid=(tr[now].l+tr[now].r)/;

         if(r<=mid)  return getmin(lc,l,r);

    else if(mid+<=l)return getmin(rc,l,r);

    else return min(getmin(lc,l,mid),getmin(rc,mid+,r));

}

int f[];

int main()

{

    int n,L,R;

    scanf("%d%d%d",&n,&L,&R);L++,R++;

    for(int i=;i<=n;i++)

    {

        scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].d);

        a[i].l++,a[i].r++;

        if(a[i].r<L||R<a[i].l)i--,n--;

        if(a[i].l<L)a[i].l=L;

        if(R<a[i].r)a[i].r=R;

    }

    sort(a+,a+n+,cmp);

    int top=; trlen=,bt(L,R);

    memset(f,,sizeof(f));

    for(int i=L;i<=R;i++)

    {

        while(top<=n&&a[top].r==i)

        {

            if(a[top].l==L)

            {

                if(a[top].d<f[i])

                    f[i]=a[top].d, change(,i,f[i]);

            }

            else

            {

                int k=getmin(,a[top].l-,a[top].r-)+a[top].d;

                if(k<f[i])

                    f[i]=k, change(,i,f[i]);

            }

            top++;

        }

    }

    if(f[R]==f[])printf("-1\n");

    else printf("%d\n",f[R]);

    return ;

}

poj3171

hdu5542 f[i][j]表示枚举到第几个位置，长度为j的严格上升序列有多少（注意一定包括第i个位置）

f[i][j]=∑(k<j&&a[k]<a[j])f[k][j-1] 这里先离散化，然后开m个树状数组记录，想想cdq分治，时间维有序第一个限制不管，第二个用树状数组解决。实际操作中，是不用定义数组的，直接插入树状数组中相应位置即可。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int mod=1e9+;

int lslen;int s[][];

int lowbit(int x){return x&-x;}

void change(int x,int w,int k)

{

    while(x<=lslen)

    {

        s[w][x]=(s[w][x]+k)%mod;

        x+=lowbit(x);

    }

}

int getsum(int x,int w)

{

    int ret=;

    while(x>)

    {

        ret=(ret+s[w][x])%mod;

        x-=lowbit(x);

    }

    return ret;

}

//----------------bit---------------------

int a[],ls[];

int main()

{

    int T,T_T=;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        lslen=;

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]), ls[++lslen]=a[i];

        sort(ls+,ls+lslen+);

        lslen=unique(ls+,ls+lslen+)-ls-;

        for(int i=;i<=n;i++)

            a[i]=lower_bound(ls+,ls+lslen+,a[i])-ls;

        memset(s,,sizeof(s));

        for(int i=;i<=n;i++)

        {

            change(a[i],,);

            int li=min(i,m);

            for(int j=;j<=li;j++)

                change(a[i],j,getsum(a[i]-,j-));

        }

        printf("Case #%d: %d\n",++T_T,getsum(lslen,m));

    }

    return ;

}

hdu5542

巴特西

0x58 数据结构优化DP

最新文章

热门文章