首页 技术 正文
技术 2022年11月23日
0 收藏 554 点赞 3,994 浏览 2109 个字

BZOJ5125: [Lydsy1712月赛]小Q的书架(DP决策单调性)

题意:N个数,按顺序划分为K组,使得逆序对之和最小。

思路:之前能用四边形不等式写的,一般网上都还有DP单调性分治的做法,今天也尝试用后者写(抄)了一遍。即:

分成K组,我们进行K-1次分治,get(l,r,L,R)中如果mid位置的最优解来自MID,那么分别以mid和MID和分界线,有get(l,mid-1,L,MID);get(mid+1,r,MID,R);

区间逆序对没有什么特别高效的方法,我们用莫对跑ok了。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int a[maxn],sum[maxn],dp[maxn],ans[maxn],N,K,ql,qr,cost;
inline int query(int x){int res=;while(x){ res+=sum[x]; x-=(-x)&x;} return res;}
inline void add(int x,int val){while(x<=N){ sum[x]+=val; x+=(-x)&x;} }
inline void move(int l,int r)
{
while(ql>l) cost+=query(a[--ql]-),add(a[ql],);
while(qr<r) cost+=query(N)-query(a[++qr]),add(a[qr],);
while(ql<l) add(a[ql],-),cost-=query(a[ql++]-);
while(qr>r) add(a[qr],-),cost-=query(N)-query(a[qr--]);
}
inline void get(int l,int r,int L,int R)
{
if(l>r) return ;
int mid=(l+r)>>,Mid;
for(int i=min(R+,mid);i>L;i--){
move(i,mid);
if(dp[i-]+cost<ans[mid]) {ans[mid]=dp[i-]+cost; Mid=i-;}
}
get(l,mid-,L,Mid); get(mid+,r,Mid,R);
}
int main()
{
scanf("%d%d",&N,&K);
rep(i,,N) scanf("%d",&a[i]);
rep(i,,N) ans[i]=ans[i-]+query(N)-query(a[i]),add(a[i],);
ql=; qr=N; cost=ans[N];
rep(i,,K){
memcpy(dp,ans,sizeof(ans)); //把上一轮的结果复制
memset(ans,0x3f,sizeof(ans));
get(,N,,N-);
}
printf("%d\n",ans[N]);
return ;
}

我也写了四边形不等式来优化DP,其他部分一样。 然而T了,估计是莫对跑得太多了。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int a[maxn],sum[maxn],dp[maxn][],pos[maxn][],N,K,ql,qr,cost;
inline int query(int x){int res=;while(x){ res+=sum[x]; x-=(-x)&x;} return res;}
inline void add(int x,int val){while(x<=N){ sum[x]+=val; x+=(-x)&x;} }
inline void move(int l,int r)
{
while(ql>l) cost+=query(a[--ql]-),add(a[ql],);
while(qr<r) cost+=query(N)-query(a[++qr]),add(a[qr],);
while(ql<l) add(a[ql],-),cost-=query(a[ql++]-);
while(qr>r) add(a[qr],-),cost-=query(N)-query(a[qr--]);
}
int main()
{
scanf("%d%d",&N,&K);
rep(i,,N) scanf("%d",&a[i]);
memset(dp,0x3f,sizeof(dp)); dp[][]=;
rep(i,,N) dp[i][]=dp[i-][]+query(N)-query(a[i]),add(a[i],);
ql=; qr=N; cost=dp[N][];
rep(i,,K){
rep(j,,N){
int L=pos[j][i-]?pos[j][i-]:;
int R=pos[j+][i]?pos[j+][i]:N-;
rep(k,L,R) {
if(k>=j) continue;
move(k+,j);
if(dp[j][i]>dp[k][i-]+cost){
dp[j][i]=dp[k][i-]+cost;
pos[j][i]=k;
}
}
}
}
printf("%d\n",dp[N][K]);
return ;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141123.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:7,142
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:4,476
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:567 阅读:5,291
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,163
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:6,335
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,874