看题解时全程:wow

题意:给出n个数,将其按顺序分为k组,令每组的价值为该组不同的数的个数。求一种分法,使得所有组价值和最大。

解:设dp[i][j]为将前 j 个数分为 i 组时的最大价值,显然有dp[i][j]=max(dp[i-1][k]+sum[k+1…j]),sum[k+1…j]为[k+1…j]中不同数的个数。然后优化求解过程,先解决sum怎么求。设原数组为a[i],令c[i]为区间[i, n]内不同数的个数,pre[i]为a[i]最后一次出现的位置,那么对于每一个i,c[pre[i]+1…i]+1,最终结果即为数组定义。意思是在pre[i]+1到i之间没有出现过a[i],那么它可以对答案贡献1,并且这样做不会有重复加的情况出现。

以样例3为例:

a:   7 7 8 7 7 8 1 7

pre+1:1 2 1 3 5 4 1 6

index:   1 2 3 4 5 6 7 8

c:   3 3 3 3 3 3 2 1

然后再来看这道题。通常我们先枚举i,再枚举j,也就是一个数一个数往里加。每添加一个数j,就可以获得所有的[k+1…j],很快乐,直接在dp[i-1]上加然后求最大值即可。区间加和求最大值的数据结构显然用线段树。注意给dp[i][k]加上c[k+1]的值,不是c[k]。

代码:


#include <bits/stdc++.h>
using namespace std;
#define maxx 35005
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 2520
int a[maxx]={0};
int dp[55][maxx]={0};
int pre[maxx]={0},pos[maxx]={0};
struct node{
    int val,lazy;
}tr[maxx*4];
void pushup(int now){
    tr[now].val=max(tr[now*2].val,tr[now*2+1].val);
}
void pushdown(int now){
    if(!tr[now].lazy){
        return;
    }
    tr[now*2].lazy+=tr[now].lazy;
    tr[now*2+1].lazy+=tr[now].lazy;
    tr[now*2].val+=tr[now].lazy;
    tr[now*2+1].val+=tr[now].lazy;
    tr[now].lazy=0;
}
int ii;
void build(int now,int l,int r){
    if(l==r){
        tr[now].val=dp[ii][l-1];
        tr[now].lazy=0;
        return ;
    }
    tr[now].lazy=0;
    int mid=(l+r)/2;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    pushup(now);
}
void add(int now,int l,int r,int s,int e){
    if(s<=l&&r<=e){
        tr[now].val+=1;
        tr[now].lazy+=1;
        return;
    }
    pushdown(now);
    int mid=(l+r)/2;
    if(s<=mid) add(now*2,l,mid,s,e);
    if(mid<e) add(now*2+1,mid+1,r,s,e);
    pushup(now);
}
int query(int now,int l,int r,int s,int e){
    if(s<=l&&r<=e){
        return tr[now].val;
    }
    pushdown(now);
    int mid=(l+r)/2;
    int res=0;
    if(s<=mid) res=max(res, query(now*2,l,mid,s,e));
    if(mid<e) res=max(res, query(now*2+1,mid+1,r,s,e));
    return res;
}

signed main() {
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        pre[i]=pos[a[i]]+1;
        pos[a[i]]=i;
    }
    for(int i=1;i<=k;i++){
        ii=i-1;
        build(1,1,n);
        for(int j=1;j<=n;j++){
            add(1,1,n,pre[j],j);
            dp[i][j]= query(1,1,n,1,j);
        }
    }
    printf("%d\n",dp[k][n]);
    return 0;
}
//dp[i][j] the first j th num, distribute into i blocks
//dp[i][j]=max(dp[i-1][k]+sum[k+1...j])

View Code

 

原文地址:http://www.cnblogs.com/capterlliar/p/16912969.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性