此题可用决策单调性来做
证明 略
引入
思路
于是此题便可先用分治优化决策单调性
时间 (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
",dp[n][k]);
return 0;
}
考虑优化
观察代码 发现(cost)(查询区间不同数个数)就有一层(n)
考虑降成(O(1)) 但预处理是(O(n^2))
于是只能降成(O(log_2^n))
从我们学习的数据结构中寻找
发现主席树恰好可以胜任
用主席树(A)掉这道题
再粘过来就行了
然而我这道题写的莫队 现在又写了一遍主席树 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
",dp[n][k]);
return 0;
}