对于只考虑首位状态的 DP, 考虑用倍增优化
P1081 开车旅行
https://www.luogu.org/problemnew/show/P1081
- const int N=100005;
- struct node{int x,y;};
- il bool operator <(node a,node b){return a.y<b.y;}
- typedef set<node> st;
- typedef st::iterator itr;
- st s;itr it,lt,rt;
- int ii,ga[N],gb[N],t,f[18][N][2],g[10],m,h[N],n,ans;
- ll ansA,ansB,a[18][N][2],b[18][N][2],A,B;
- il bool cmp(int a,int b)
- {
- return abs(h[a]-h[ii]) <abs(h[b]-h[ii]) || (abs(h[a]-h[ii]) == abs(h[b]-h[ii]) && h[a]<h[b]);
- }
- il void pre()
- {
- n=rd();
- FOR(i,1,n) h[i]=rd();
- for(ii=n;ii;--ii)
- {
- node p=(node){ii,h[ii]};
- s.insert(p);
- it=s.find(p);
- lt=it,rt=it,m=0;
- if(lt!=s.begin()) lt--,g[++m]=lt->x;
- if(lt!=s.begin()) lt--,g[++m]=lt->x;
- if(rt++,rt!=s.end())
- {
- g[++m]=rt->x;
- if(rt++,rt!=s.end()) g[++m]=rt->x;
- }
- sort(g+1,g+m+1,cmp);
- if(m) gb[ii]=g[1];
- if(m>1) ga[ii]=g[2];
- }
- }
- View Code
- il void work()
- {
- FOR(i,1,n)
- {
- if(ga[i]) f[0][i][0]=ga[i],a[0][i][0]=abs(h[ga[i]]-h[i]);
- if(gb[i]) f[0][i][1]=gb[i],b[0][i][1]=abs(h[gb[i]]-h[i]);
- }
- t=(int)(log(n*1.0)/log(2.0)+0.001);
- FOR(i,1,t) FOR(j,1,n) FOR(k,0,1)
- {
- int l;
- if(i==1) l=k^1; else l=k;
- if(f[i-1][j][k]) f[i][j][k]=f[i-1][f[i-1][j][k]][l];
- if(f[i][j][k])
- {
- a[i][j][k]=a[i-1][j][k]+a[i-1][f[i-1][j][k]][l];
- b[i][j][k]=b[i-1][j][k]+b[i-1][f[i-1][j][k]][l];
- }
- }
- }
- il void solve(int s,int x0,ll &A,ll &B)
- {
- A=B=0;int k=0;
- For(i,t,0)
- if(f[i][s][k]&&a[i][s][k]+b[i][s][k]<=x0)
- {
- x0-=a[i][s][k]+b[i][s][k];
- A+=a[i][s][k],B+=b[i][s][k];
- if(i==0) k^=1;
- s=f[i][s][k];
- }
- }
- il void print()
- {
- int x0=rd();
- ansA=1,ansB=0;
- FOR(i,1,n)
- {
- solve(i,x0,A,B);
- if(!B) A=1;
- if(A*ansB <B*ansA || (A*ansB==B*ansA && h[i]>h[ans])) ansA=A,ansB=B,ans=i;
- }
- printf("%d\n",ans);
- m=rd();
- FOR(i,1,m)
- {
- int x=rd(),y=rd();
- solve(x,y,A,B);
- printf("%lld %lld\n",A,B);
- }
- }
- int main()
- {
- pre();
- work();
- print();
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3009884.html