Noip2012 开车旅行

题目链接：Click here

Solution:

注意到每个点的决策都是一定的，我们排序后通过双向链表来处理这个东西

设\(A[i][j]\)表示从\(i\)出发，走了\(2^j\)轮时\(A\)开车的距离，\(B[i][j]\)同理

\(f[i][j]\)则表示\(2^j\)轮后的位置，倍增优化dp即可

Code:

#include
#define int long long
using namespace std;
const int N=1e5+11;
const int inf=3e9;
int n,m,ans,Aa,Ab,h[N],id[N],pre[N],nxt[N],p[N];
int f[N][20],A[N][20],B[N][20],mn[N],nmn[N];
inline bool cmp(int a,int b){return h[a]hdlt(i,id[nt])) nmn[i]=nt;
        if(hdlt(i,id[nmn[i]])>hdlt(i,id[pe])) nmn[i]=pe;
        if(hdlt(i,id[nmn[i]])==hdlt(i,id[nt])&&h[id[nt]]=0;i--)
        if(f[x][i]&&A[x][i]+B[x][i]<=limit){
            a+=A[x][i],b+=B[x][i];
            limit-=A[x][i]+B[x][i];
            x=f[x][i];
        }
    if(hdlt(nmn[x],x)<=limit) a+=hdlt(nmn[x],x);
}
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++)
        h[i]=read(),id[i]=i;
    sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;i++)
        pre[i]=i-1,nxt[i]=i+1,p[id[i]]=i;
    prepare();trans();
    int Limit=read();m=read();
    for(int i=1;i<=n;i++){
        int a,b;calc(a,b,Limit,i);
        if(!ans||a*Ab