此题可用决策单调性来做

证明 略

引入

决策单调性(\(My blog\))

思路

于是此题便可先用分治优化决策单调性

时间 \(O(n^2*k)\) \(101 tests\) 中 只能过前\(9\)个 \(9pts\) ?

#include <map>
#include <string>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0,f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
const int MAXN = 35010,inf = MAXN;
int a[MAXN],dp[MAXN][55];
bool vis[MAXN];
inline int cost(int l,int r)
{
    int res = 0;
    for(reg i = l;i <= r;i++)
    {
        if(!vis[a[i]]) res++;
        vis[a[i]] = 1;
    }
    for(reg i = 1;i <= r;i++) vis[a[i]] = 0;    
    return res;
}
inline void dfs(int k,int l,int r,int opl,int opr)
{
    if(l > r) return;
    int mid = l + r >> 1,maxl = -inf,id;
    for(reg i = opl;i <= min(opr,mid);i++)
    {
        int cur = dp[i - 1][k - 1] + cost(i,mid);
        if(cur > maxl) maxl = cur,id = i;
    }
    dp[mid][k] = maxl;
    dfs(k,l,mid - 1,opl,id);
    dfs(k,mid + 1,r,id,opr);
}
int main()
{
    int n = Read(1),k = Read(1);
    for(reg i = 1;i <= n;i++)
        a[i] = Read(1);
    for(reg i = 1;i <= k;i++) dfs(i,1,n,1,n);
    printf("%d\n",dp[n][k]);
    return 0;
}

考虑优化

观察代码 发现\(cost\)(查询区间不同数个数)就有一层\(n\)

考虑降成\(O(1)\) 但预处理是\(O(n^2)\)

于是只能降成\(O(log_2^n)\)

从我们学习的数据结构中寻找

发现主席树恰好可以胜任

用主席树\(A\)掉这道题

SP3267 DQUERY - D-query

再粘过来就行了

然而我这道题写的莫队 现在又写了一遍主席树 233

\(Code\)

时间复杂度 \(O(n*log_2^n*k)\)

#include <map>
#include <string>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0,f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
const int MAXN = 35010,inf = MAXN;
int a[MAXN],dp[MAXN][55],n,k;
namespace segment_tree
{
    struct node
    {
        int l,r,val;
    }tree[MAXN * 40];
    map<int,int> vis;
    int cnt,root[MAXN];
    inline int update(int k,int l,int r,int pos,int v)
    {
        tree[++cnt] = tree[k],tree[cnt].val += v;
        k = cnt;
        if(l == r) return k;
        int mid = l + r >> 1;
        if(pos <= mid) tree[k].l = update(tree[k].l,l,mid,pos,v);
        else tree[k].r = update(tree[k].r,mid + 1,r,pos,v);
        return k;
    }
    inline int query(int k,int pos,int l,int r)
    {
        if(l >= pos) return tree[k].val;
        int mid = l + r >> 1;
        if(pos <= mid) return query(tree[k].l,pos,l,mid) + tree[tree[k].r].val;
        return query(tree[k].r,pos,mid + 1,r);
    }
    inline void init()
    {
        n = Read(1),k = Read(1);
        root[0] = tree[0].l = tree[0].r = tree[0].val = 0;
        for(reg i = 1;i <= n;i++)
        {
            int x = Read(1);
            if(!vis[x]) root[i] = update(root[i - 1],1,n,i,1);
            else {
                int k = update(root[i - 1],1,n,vis[x],-1);
                root[i] = update(k,1,n,i,1);
            }
            vis[x] = i;
        }
    }
}
using namespace segment_tree;
inline int cost(int l,int r) {return query(root[r],l,1,n);}
inline void dfs(int k,int l,int r,int opl,int opr)
{
    if(l > r) return;
    int mid = l + r >> 1,maxl = -inf,id;
    for(reg i = opl;i <= min(opr,mid);i++)
    {
        int cur = dp[i - 1][k - 1] + cost(i,mid);
        if(cur > maxl) maxl = cur,id = i;
    }
    dp[mid][k] = maxl;
    dfs(k,l,mid - 1,opl,id);
    dfs(k,mid + 1,r,id,opr);
}
int main()
{
    init();
    for(reg i = 1;i <= k;i++) dfs(i,1,n,1,n);
    printf("%d\n",dp[n][k]);
    return 0;
}