倍增优化DP

对于只考虑首位状态的DP，考虑用倍增优化

P1081 开车旅行

https://www.luogu.org/problemnew/show/P1081

 1 const int N=100005;
 2 struct node{int x,y;};
 3 il bool operator <(node a,node b){return a.y<b.y;}
 4 typedef set<node> st;
 5 typedef st::iterator itr;
 6 st s;itr it,lt,rt;
 7 int ii,ga[N],gb[N],t,f[18][N][2],g[10],m,h[N],n,ans;
 8 ll ansA,ansB,a[18][N][2],b[18][N][2],A,B;
 9 
10 il bool cmp(int a,int b)
11 {
12       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]);
13 }
14 
15 il void pre()
16 {
17           n=rd();
18       FOR(i,1,n) h[i]=rd();
19       for(ii=n;ii;--ii)
20     {
21           node p=(node){ii,h[ii]};
22           s.insert(p);
23           it=s.find(p);
24           lt=it,rt=it,m=0;
25           if(lt!=s.begin()) lt--,g[++m]=lt->x;
26           if(lt!=s.begin()) lt--,g[++m]=lt->x;
27           if(rt++,rt!=s.end())
28         {
29               g[++m]=rt->x;
30               if(rt++,rt!=s.end()) g[++m]=rt->x;
31         }    
32           sort(g+1,g+m+1,cmp);
33           if(m) gb[ii]=g[1];
34           if(m>1) ga[ii]=g[2];
35     }
36 }

View Code

 1 il void work()
 2 {
 3     FOR(i,1,n)
 4     {
 5         if(ga[i]) f[0][i][0]=ga[i],a[0][i][0]=abs(h[ga[i]]-h[i]);
 6         if(gb[i]) f[0][i][1]=gb[i],b[0][i][1]=abs(h[gb[i]]-h[i]);
 7     }
 8     t=(int)(log(n*1.0)/log(2.0)+0.001);
 9     FOR(i,1,t) FOR(j,1,n) FOR(k,0,1)
10     {
11         int l;
12         if(i==1) l=k^1; else l=k;
13         if(f[i-1][j][k]) f[i][j][k]=f[i-1][f[i-1][j][k]][l];
14         if(f[i][j][k])
15         {
16             a[i][j][k]=a[i-1][j][k]+a[i-1][f[i-1][j][k]][l];
17             b[i][j][k]=b[i-1][j][k]+b[i-1][f[i-1][j][k]][l];
18         }    
19     }
20 }

 1 il void solve(int s,int x0,ll &A,ll &B)
 2 {
 3       A=B=0;int k=0;
 4       For(i,t,0)
 5     if(f[i][s][k]&&a[i][s][k]+b[i][s][k]<=x0)
 6     {
 7         x0-=a[i][s][k]+b[i][s][k];
 8         A+=a[i][s][k],B+=b[i][s][k];
 9         if(i==0) k^=1;
10         s=f[i][s][k];
11     }
12 }
13 
14 il void print()
15 {
16       int x0=rd();
17       ansA=1,ansB=0;
18       FOR(i,1,n)
19     {
20           solve(i,x0,A,B);
21           if(!B) A=1;
22           if(A*ansB < B*ansA || (A*ansB==B*ansA && h[i]>h[ans])) ansA=A,ansB=B,ans=i;
23     }
24       printf("%d
",ans);
25       m=rd();
26       FOR(i,1,m)
27     {
28           int x=rd(),y=rd();
29           solve(x,y,A,B);
30           printf("%lld %lld
",A,B);
31     }
32 }
33 
34 int main()
35 {
36       pre();
37       work();
38       print();
39       return 0;
40 }

View Code