做题时间:2022.10.15
\(【题目描述】\)
给定一个长度为 \(n(2\leq n\leq 10^5)\) 的序列,把他分成 \(k(2\leq k\leq \min(n,20))\) 个子段,每个子段的花费是其中相同元素的对数,求所有子段的花费之和的最小值。
\(【输入格式】\)
第一行两个整数 \(n,k\)
第二行 \(n\) 个整数表示序列
\(【输出格式】\)
一行一个整数表示答案
\(【考点】\)
决策单调性优化dp、莫队
\(【做法】\)
设 \(f_{i,j}\) 表示将前 \(i\) 个数分割成 \(j\) 个子段的花费,有:
\[f_{i,j}=\min\limits_{k=1}^{i}(f_{k,j-1}+val(k+1,j)) \]
然后套路地使用分治去做。比较麻烦的是计算 \(val(l,r)\),可以使用类似于莫队的思想,直接全局维护当前的求解区间 \([L,R]\),然后每次计算的时候暴力移动左右端点即可。这相当于每层递归移动完父亲后移动儿子,因此单层的复杂度为 \(O(n)\),总时间复杂度为 \(O(n\log n)\)
\(【代码】\)
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+50,K=22;
int a[N],n,k;
ll f[N][K],ans;
int buc[N],L=1,R;
void add(int x){ans+=(ll)buc[x],buc[x]++;}//添加一个点
void del(int x){buc[x]--,ans-=(ll)buc[x];}//删除一个点
ll calc(int l,int r)//暴力移动并计算val[l,r]
{
while(L>l) L--,add(a[L]);
while(L<l) del(a[L]),L++;
while(R<r) R++,add(a[R]);
while(R>r) del(a[R]),R--;
return ans;
}
void dp(int l,int r,int jl,int jr,int cur)
{
if(l>r) return ;
int mid=(l+r)>>1;
int num=jl;
for(int k=jl;k<=min(jr,mid);k++){
ll t=f[k][cur-1]+calc(k+1,mid);
if(t<f[mid][cur]) f[mid][cur]=t,num=k;
}
dp(l,mid-1,jl,num,cur);
dp(mid+1,r,num,jr,cur);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=k;i++) dp(1,n,0,n-1,i);
printf("%lld\n",f[n][k]);
return 0;
}
原文地址:http://www.cnblogs.com/Unlimited-Chan/p/16794561.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性