[BZOJ3688]折线统计（dp+bit优化）

2019-11-14 12:38:22

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

n2k $n^2k$ 的dp是比较好想好写的 f(i,j,0/1)表示划分了i段，以第j个结尾，最后一段是上升0/下降1的方案数 f(i,j,0)=∑k=i+1j−1∑y(k)<y(j)f(i,k,0)+∑k=i+1j−1∑y(k)>y(j)f(i−1,k,1) $f(i,j,0)=/sum/limits_{k=i+1}^{j-1}/sum/limits_{y(k)<y(j)}f(i,k,0)+/sum/limits_{k=i+1}^{j-1}/sum/limits_{y(k)>y(j)}f(i-1,k,1)$ f(i,j,1)=∑k=i+1j−1∑y(k)<y(j)f(i−1,k,0)+∑k=i+1j−1∑y(k)>y(j)f(i,k,1) $f(i,j,1)=/sum/limits_{k=i+1}^{j-1}/sum/limits_{y(k)<y(j)}f(i-1,k,0)+/sum/limits_{k=i+1}^{j-1}/sum/limits_{y(k)>y(j)}f(i,k,1)$ 两个限制条件，第一个边做边维护，第二个用bit维护前缀和，01分开维护，滚动数组然后就是O(nlogn) $O(nlogn)$ 了

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define Mod 100007#define N 50005#define inf 100000int n,k,ans;struct data{int x,y;}p[N];int f[15][N][2],C[2][2][inf+5];int cmp(data a,data b){ return a.x<b.x;}void add(int loc,int val,int id,int jd){ for (int i=loc;i<=inf;i+=i&-i) C[id][jd][i]=(C[id][jd][i]+val)%Mod;}int query(int loc,int id,int jd){ int ans=0; for (int i=loc;i>=1;i-=i&-i) ans=(ans+C[id][jd][i])%Mod; return ans;}int main(){ scanf("%d%d",&n,&k); for (int i=1;i<=n;++i) scanf("%d%d",&p[i].x,&p[i].y); sort(p+1,p+n+1,cmp); for (int i=1;i<=n;++i) { f[0][i][0]=f[0][i][1]=1; add(p[i].y,f[0][i][0],0,0); add(p[i].y,f[0][i][1],0,1); } for (int i=1;i<=k;++i) { memset(C,0,sizeof(C)); add(p[i].y,f[i-1][i][0],(i-1)&1,0); add(p[i].y,f[i-1][i][1],(i-1)&1,1); for (int j=i+1;j<=n;++j) { f[i][j][0]=f[i][j][0]+query(p[j].y-1,(i-1)&1,1)+query(p[j].y-1,i&1,0); f[i][j][1]=f[i][j][1]+query(inf,(i-1)&1,0)-query(p[j].y,(i-1)&1,0)+query(inf,i&1,1)-query(p[j].y,i&1,1); f[i][j][0]=(f[i][j][0]%Mod+Mod)%Mod; f[i][j][1]=(f[i][j][1]%Mod+Mod)%Mod; add(p[j].y,f[i][j][0],i&1,0); add(p[j].y,f[i][j][1],i&1,1); add(p[j].y,f[i-1][j][0],(i-1)&1,0); add(p[j].y,f[i-1][j][1],(i-1)&1,1); } } for (int i=1;i<=n;++i) ans=(ans+f[k][i][0]+f[k][i][1])%Mod; PRintf("%d/n",ans);}

上一篇：人民币小写转大写函数在网上找的，不错

下一篇：中级java工程师面试题

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注