@KirinBill
2018-03-27T20:42:15.000000Z
字数 18697
阅读 2114
动态规划
目录
又由于自变量单调递增,我们可以用双端队列维护下凸壳,从队首到队尾斜率单调递减,具体过程如下:
这样的话,维护凸壳的均摊复杂度就是的了,于是这题总复杂度就由降到了
代码:
#include <cstdio>
const int MAXN=50005;
int n,l;
long long k[MAXN],dp[MAXN];
inline long long sqr(register long long x){return x*x;}
//intercept
inline long long y_itcpt(int i){
return sqr(k[i])+(l*k[i]<<1)+dp[i];
}
inline long long slope(int i){return -(k[i]<<1);}
inline long long cal(int i,int j){
return slope(j)*k[i]+y_itcpt(j);
}
//intersection
inline double itsct(int i,int j){
return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
}
inline long long slopeDP(){
static int dq[MAXN];
int head=0,tail=0;
for(int i=1;i<=n;++i){
while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1]))
++head;
dp[i]=cal(i,dq[head])+sqr(k[i]-l);
while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1]))
--tail;
dq[++tail]=i;
}
return dp[n];
}
int main(){
scanf("%d%d",&n,&l);
++l;
for(int i=1;i<=n;++i){
scanf("%d",&k[i]);
k[i]+=k[i-1];
}
for(int i=1;i<=n;++i)
k[i]+=i;
printf("%lld",slopeDP());
return 0;
}
代码:
#include <cstdio>
#include <algorithm>
using std::sort;
const int MAXN=50005;
int n;
long long dp[MAXN];
struct square{
int a,b;
static bool cmp_ab(const square &a,const square &b){
return a.a<b.a || (a.a==b.a && a.b<b.b);
}
}field[MAXN],tmp[MAXN];
inline int slope(int i){return field[i+1].b;}
inline long long y_itcpt(int i){return dp[i];}
inline long long cal(int i,int j){
return (long long)slope(j)*field[i].a+y_itcpt(j);
}
inline double itsct(int i,int j){
return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
}
inline long long slopeDP(){
static int dq[MAXN];
int head=0,tail=0;
for(int i=1;i<=n;++i){
while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1]))
++head;
dp[i]=cal(i,dq[head]);
while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1]))
--tail;
dq[++tail]=i;
}
return dp[n];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&tmp[i].a,&tmp[i].b);
sort(tmp+1,tmp+n+1,square::cmp_ab);
int cnt=0;
for(int i=1;i<=n;++i){
while(cnt && field[cnt].b<=tmp[i].b)
--cnt;
field[++cnt]=tmp[i];
}
n=cnt;
printf("%lld",slopeDP());
return 0;
}
代码:
#include <cstdio>
const int MAXN=1000005;
int n;
int dis[MAXN],c[MAXN],p[MAXN];
long long sum[MAXN],sum_dis[MAXN],dp[MAXN];
inline long long slope(int i){return sum[i];}
inline long long y_itcpt(int i){return dp[i]-sum_dis[i];}
inline long long cal(int i,int j){
return slope(j)*dis[i]+y_itcpt(j);
}
inline double itsct(int i,int j){
return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
}
inline long long slopeDP(){
static int dq[MAXN];
int head=0,tail=0;
for(int i=1;i<=n;++i){
while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1]))
++head;
dp[i]=cal(i,dq[head])+c[i]-dis[i]*sum[i]+sum_dis[i];
while(head<tail && itsct(i,dq[tail-1])>=itsct(dq[tail],dq[tail-1]))
--tail;
dq[++tail]=i;
}
return dp[n];
}
inline void pre_cal(){
for(int i=1;i<=n;++i){
dis[i]=dis[n]-dis[i];
sum[i]=sum[i-1]+p[i];
sum_dis[i]=sum_dis[i-1]+(long long)p[i]*dis[i];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d%d",&dis[i],&p[i],&c[i]);
pre_cal();
printf("%lld",slopeDP());
return 0;
}
代码:
#include <cstdio>
const int MAXN=1000005;
int n;
int a[MAXN],b[MAXN];
long long sum[MAXN],sum_dis[MAXN],dp[MAXN];
inline long long slope(int i){return sum[i];}
inline long long y_itcpt(int i){
return dp[i]-sum_dis[i];
}
inline long long cal(int i,int j){
return slope(j)*(n-i)+y_itcpt(j);
}
inline double itsct(int i,int j){
return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
}
inline long long slopeDP(){
static int dq[MAXN];
int head=0,tail=0;
for(int i=1;i<=n;++i){
while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1]))
++head;
dp[i]=cal(i,dq[head])+sum_dis[i]-(n-i)*sum[i]+a[i];
while(head<tail && itsct(i,dq[tail-1])>=itsct(dq[tail],dq[tail-1]))
--tail;
dq[++tail]=i;
}
return dp[n];
}
inline void pre_cal(){
for(int i=1;i<=n;++i){
sum[i]=sum[i-1]+b[i];
sum_dis[i]=sum_dis[i-1]+(long long)(n-i)*b[i];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
scanf("%d",&b[i]);
pre_cal();
printf("%lld",slopeDP());
return 0;
}
代码:
#include <cstdio>
const int MAXN=1e6+5;
int n;
int a[MAXN];
long long dp[MAXN];
inline long long sqr(register long long x){return x*x;}
inline int slope(int i){return -i;}
inline long long y_itcpt(int i){
return dp[i]+(sqr(i)+i>>1);
}
inline long long cal(int i,int j){
return (long long)slope(j)*i+y_itcpt(j);
}
inline double itsct(int i,int j){
return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
}
inline long long slopeDP(){
static int dq[MAXN];
int head=0,tail=0;
for(int i=1;i<=n;++i){
while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1]))
++head;
dp[i]=cal(i,dq[head])+(sqr(i)-i>>1)+a[i];
while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1]))
--tail;
dq[++tail]=i;
}
return dp[n];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
printf("%lld",slopeDP());
return 0;
}
代码:
#include <cstdio>
const int MAXN=1000005;
int n,a,b,c;
int sum[MAXN];
long long dp[MAXN];
inline long long sqr(register long long x){return x*x;}
inline long long slope(int i){
return (long long)-(a<<1)*sum[i];
}
inline long long y_itcpt(int i){
return dp[i]+a*sqr(sum[i])-(long long)b*sum[i];
}
inline long long cal(int i,int j){
return slope(j)*sum[i]+y_itcpt(j);
}
inline double itsct(int i,int j){
return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
}
inline long long slopeDP(){
static int dq[MAXN];
int head=0,tail=0;
for(int i=1;i<=n;++i){
while(head<tail && cal(i,dq[head])<=cal(i,dq[head+1]))
++head;
dp[i]=cal(i,dq[head])+a*sqr(sum[i])+(long long)b*sum[i]+c;
while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1]))
--tail;
dq[++tail]=i;
}
return dp[n];
}
int main(){
scanf("%d",&n);
scanf("%d%d%d",&a,&b,&c);
for(int i=1;i<=n;++i){
scanf("%d",&sum[i]);
sum[i]+=sum[i-1];
}
printf("%lld",slopeDP());
return 0;
}
代码:
#include <cstdio>
const int MAXN=3005;
int n,m;
int sum[MAXN];
long long dp[MAXN][MAXN];
inline long long sqr(register long long x){return x*x;}
inline long long slope(int i){return -(sum[i]<<1);}
inline long long y_itcpt(int i,int k){
return dp[k][i]+sqr(sum[i]);
}
inline long long cal(int i,int j,int k){
return slope(j)*sum[i]+y_itcpt(j,k);
}
inline double itsct(int i,int j,int k){
return (double)(y_itcpt(j,k)-y_itcpt(i,k))/(slope(i)-slope(j));
}
inline long long slopeDP(){
static int dq[MAXN];
for(int i=1;i<=n;++i)
dp[1][i]=sqr(sum[i]);
for(int i=2,head,tail;i<=m;++i){
head=tail=0,dq[0]=i-1;
for(int j=i;j<=n;++j){
while(head<tail && cal(j,dq[head],i-1)>=cal(j,dq[head+1],i-1))
++head;
dp[i][j]=cal(j,dq[head],i-1)+sqr(sum[j]);
while(head<tail && itsct(j,dq[tail-1],i-1)<=itsct(dq[tail],dq[tail-1],i-1))
--tail;
dq[++tail]=j;
}
}
return m*dp[m][n]-sqr(sum[n]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&sum[i]);
sum[i]+=sum[i-1];
}
printf("%lld",slopeDP());
return 0;
}
代码:
#include <cstdio>
const int MAXN=100005;
//const int MAXK=205;
int n,k;
int sum[MAXN];
//int pre[MAXK][MAXN];
long long dp[2][MAXN];
inline long long sqr(register long long x){return x*x;}
inline int slope(int i){return sum[i];}
inline long long y_itcpt(int i,int k){
return dp[k&1][i]-sqr(sum[i]);
}
inline long long cal(int i,int j,int k){
return (long long)slope(j)*sum[i]+y_itcpt(j,k);
}
inline double itsct(int i,int j,int k){
return (double)(y_itcpt(j,k)-y_itcpt(i,k))/(slope(i)-slope(j));
}
inline long long slopeDP(){
static int dq[MAXN];
for(int i=1,head,tail;i<=k;++i){
for(int j=1;j<=i;++j)
dp[i&1][j]=0;
head=tail=0,dq[0]=i;
for(int j=i+1;j<=n;++j){
while(head<tail && cal(j,dq[head],i-1)<=cal(j,dq[head+1],i-1))
++head;
//pre[i][j]=dq[head];
dp[i&1][j]=cal(j,dq[head],i-1);
while(head<tail && itsct(j,dq[tail-1],i-1)<=itsct(dq[tail],dq[tail-1],i-1))
--tail;
if(slope(j)!=slope(dq[tail])) dq[++tail]=j;
}
}
return dp[k&1][n];
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i){
scanf("%d",&sum[i]);
sum[i]+=sum[i-1];
}
printf("%lld",slopeDP());
/*
putchar('\n');
for(int i=k,j=n;i;--i){
j=pre[i][j];
printf("%d ",j);
}
*/
return 0;
}
上面的练习都有一个共同的特点,就是自变量是单调的,这样我们每次可以将双端队列的开头直线不断弹出,让对于当前自变量的最优决策在队首。然而有一些题比较坑,自变量并不单调,这时我们不能再像之前那样弹队首了,只能通过二分来查找对于当前自变量的最优决策了。
1.[SDOI 2012] 任务安排
BZOJ上题面不完整。。。
任务按标号从~的顺序分批完成,不是任意顺序。
INT_MAX
LLONG_MAX
.
deque
变成stack
了,但是怎么快速找到自变量对应的最优决策是哪条直线呢?其实这是可以二分的,因为相邻的每两条直线的交点都是最优决策直线改变的界限: 代码:
#include <cstdio>
const int MAXN=300005;
int n,s,top;
int stk[MAXN];
long long sumt[MAXN],sumf[MAXN],dp[MAXN];
inline long long slope(int i){return -sumf[i];}
inline long long y_itcpt(int i){
return dp[i]-sumf[i]*s;
}
inline long long cal(int i,int j){
return slope(j)*sumt[i]+y_itcpt(j);
}
inline double itsct(int i,int j){
return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
}
inline int bin_chop(int now){
int l=1,r=top,mid;
while(l<=r){
mid=l+r>>1;
if(itsct(stk[mid],stk[mid-1])<=sumt[now])
l=mid+1;
else r=mid-1;
}
return stk[r];
}
inline long long slopeDP(){
for(int i=1;i<=n;++i){
dp[i]=cal(i,bin_chop(i))+sumt[i]*sumf[i]+sumf[n]*s;
while(top && itsct(i,stk[top-1])<=itsct(stk[top],stk[top-1]))
--top;
if(slope(i)!=slope(stk[top])) stk[++top]=i;
}
return dp[n];
}
int main(){
scanf("%d%d",&n,&s);
for(int i=1;i<=n;++i){
scanf("%lld%lld",&sumt[i],&sumf[i]);
sumt[i]+=sumt[i-1],sumf[i]+=sumf[i-1];
}
printf("%lld",slopeDP());
return 0;
}
代码:
#include <cstdio>
const int MAXN=100005;
int n;
int v[MAXN],w[MAXN];
int he[MAXN],dis[MAXN];
int stk[MAXN];
long long dp[MAXN];
struct line{int to,nex,w;}ed[MAXN<<1];
inline void addE(int u,int v,int w){
static int cnt;
ed[++cnt]=(line){v,he[u],w};
he[u]=cnt;
}
inline int slope(int i){return -dis[i];}
inline long long y_itcpt(int i){return dp[i];}
inline long long cal(int i,int j){
return (long long)slope(j)*v[i]+dp[j];
}
inline double itsct(int i,int j){
return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
}
inline int bin_chop_ln(int now,int r){
int l=1,mid;
while(l<=r){
mid=l+r>>1;
if(itsct(stk[mid-1],stk[mid])<=v[now])
l=mid+1;
else r=mid-1;
}
return stk[r];
}
inline long long slopeDP(int i,int top){
return cal(i,bin_chop_ln(i,top))+w[i]+(long long)v[i]*dis[i];
}
inline int bin_chop_top(int now,int r){
int l=1,mid;
while(l<=r){
mid=l+r>>1;
if(itsct(now,stk[mid-1])>itsct(stk[mid],stk[mid-1]))
l=mid+1;
else r=mid-1;
}
return r;
}
void treeDP(int u,int fa,int top){
dp[u]=slopeDP(u,top);
top=bin_chop_top(u,top);
int back_cur=++top,pre=stk[top];
stk[top]=u;
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(v!=fa){
dis[v]=dis[u]+ed[i].w;
treeDP(v,u,top);
}
}
stk[back_cur]=pre;
}
int main(){
scanf("%d",&n);
for(int i=1,u,v,w;i<n;++i){
scanf("%d%d%d",&u,&v,&w);
addE(u,v,w),addE(v,u,w);
}
for(int i=2;i<=n;++i)
scanf("%d%d",&w[i],&v[i]);
for(int i=he[1],v;i;i=ed[i].nex){
v=ed[i].to;
dis[v]=ed[i].w;
treeDP(v,1,0);
}
for(int i=2;i<=n;++i){
printf("%lld",dp[i]);
if(i!=n) putchar(' '); //卡输出
}
return 0;
}
上一个部分的题虽然自变量不单调了,但是直线斜率还是单调的,依然可以用双端队列或者栈维护。但是有些丧病的出题人把斜率也给搞的不单调了,这时只能用一些方法维护一个可以迅速从中间插入的凸壳了,传统方法是平衡树,但是那样代码量很大,常数也不小,而考虑到这里是可以离线维护的,我们可以用CDQ分治来解决(陈丹琪的论文就是用这个引入的Orz)。
代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::sort;
using std::max;
const int MAXN=100005;
int n;
double a[MAXN],b[MAXN],rate[MAXN],ans[MAXN];
struct dp_arr{
int id;
double a,b,x;
double *ans;
static bool cmp_x(const dp_arr &a,const dp_arr &b){
return a.x<b.x;
}
}dp[MAXN];
inline double slope(int i){return dp[i].a;}
inline double y_itcpt(int i){return dp[i].b;}
inline double cal(int i,int j){
return slope(j)*dp[i].x+y_itcpt(j);
}
inline double itsct(int i,int j){
return (y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j));
}
inline void separate(int l,int r){
static dp_arr tmp[MAXN];
int mid=l+r>>1;
for(int cur=l,lp=l,rp=mid+1;cur<=r;++cur){
if(dp[cur].id<=mid) tmp[lp++]=dp[cur];
else tmp[rp++]=dp[cur];
}
memcpy(dp+l,tmp+l,(r-l+1)*sizeof(dp_arr));
}
inline void slopeDP(int l,int r){
static int dq[MAXN];
int mid=l+r>>1;
int head=0,tail=0;
for(int i=l;i<=mid;++i){
while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1]))
--tail;
if(slope(i)!=slope(dq[tail])) dq[++tail]=i;
}
for(int i=mid+1;i<=r;++i){
while(head<tail && cal(i,dq[head])<=cal(i,dq[head+1]))
++head;
*dp[i].ans=max(*dp[i].ans,b[dp[i].id]*cal(i,dq[head]));
}
}
void CDQ_DC(int l,int r){
static dp_arr tmp[MAXN];
if(l==r){
//其实l=dp[l].id,但是现在dp[l-1].id可能不等于l了
//所以这样写
*dp[l].ans=max(*dp[l].ans,ans[dp[l].id-1]);
dp[l].b=*dp[l].ans/(a[l]*rate[l]+b[l]);
dp[l].a=dp[l].b*rate[l];
return;
}
separate(l,r);
int mid=l+r>>1;
CDQ_DC(l,mid);
slopeDP(l,r);
CDQ_DC(mid+1,r);
for(int cur=l,lp=l,rp=mid+1;cur<=r;++cur){
if(rp>r || (lp<=mid && dp[lp].a<=dp[rp].a))
tmp[cur]=dp[lp++];
else tmp[cur]=dp[rp++];
}
memcpy(dp+l,tmp+l,(r-l+1)*sizeof(dp_arr));
}
int main(){
scanf("%d%lf",&n,&ans[0]);
dp[0].ans=&ans[0];
for(int i=1;i<=n;++i){
scanf("%lf%lf%lf",&a[i],&b[i],&rate[i]);
dp[i].x=a[i]/b[i];
dp[i].id=i,dp[i].ans=&ans[i];
}
sort(dp+1,dp+n+1,dp_arr::cmp_x);
CDQ_DC(1,n);
printf("%.3lf",ans[n]);
return 0;
}