题目描述
小 AA 和小 BB 决定利用假期外出旅行，他们将想去的城市从 11 到 nn 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 ii 的海拔高度为hihi，城市 ii 和城市 jj 之间的距离 di,jdi,j 恰好是这两个城市海拔高度之差的绝对值，即 di,j=∣hi−hj∣di,j=∣hi−hj∣。
旅行过程中，小 AA 和小 BB 轮流开车，第一天小 AA 开车，之后每天轮换一次。他们计划选择一个城市 ss 作为起点，一直向东行驶，并且最多行驶 xx 公里就结束旅行。
小 AA 和小 BB 的驾驶风格不同，小 BB 总是沿着前进方向选择一个最近的城市作为目的地，而小 AA 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 xx 公里，他们就会结束旅行。
在启程之前，小 AA 想知道两个问题：
1、 对于一个给定的 x=x0x=x0，从哪一个城市出发，小 AA 开车行驶的路程总数与小 BB 行驶的路程总数的比值最小（如果小 BB 的行驶路程为 00，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 AA 开车行驶的路程总数与小 BB 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
2、对任意给定的 x=xix=xi 和出发城市 sisi，小 AA 开车行驶的路程总数以及小 BB 行驶的路程总数。
输入格式
第一行包含一个整数 nn，表示城市的数目。
第二行有 nn 个整数，每两个整数之间用一个空格隔开，依次表示城市 11 到城市 nn 的海拔高度，即 h1,h2...hnh1,h2...hn，且每个 hihi 都是互不相同的。
第三行包含一个整数 x0x0。
第四行为一个整数 mm，表示给定 mm 组 sisi 和 xixi。
接下来的 mm 行，每行包含 22 个整数 sisi 和 xixi，表示从城市sisi 出发，最多行驶 xixi 公里。
输出格式
输出共 m+1m+1 行。
第一行包含一个整数 s0s0，表示对于给定的 x0x0，从编号为 s0s0 的城市出发，小 AA 开车行驶的路程总数与小 BB 行驶的路程总数的比值最小。
接下来的 mm 行，每行包含 22 个整数，之间用一个空格隔开，依次表示在给定的 sisi 和 xixi 下小 AA 行驶的里程总数和小 BB 行驶的里程总数。
输入输出样例
输入 #14 2 3 1 4 3 4 1 3 2 3 3 3 4 3输出 #1
1 1 1 2 0 0 0 0 0输入 #2
10 4 5 6 1 2 3 7 8 9 10 7 10 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7输出 #2
2 3 2 2 4 2 1 2 4 5 1 5 1 2 1 2 0 0 0 0 0
说明/提示
【样例1说明】
各个城市的海拔高度以及两个城市间的距离如上图所示。
如果从城市 11 出发，可以到达的城市为 2,3,42,3,4，这几个城市与城市 11 的距离分别为 1,1,21,1,2，但是由于城市 33 的海拔高度低于城市 22，所以我们认为城市 33 离城市 11 最近，城市 22 离城市 11 第二近，所以小A会走到城市 22。到达城市 22 后，前面可以到达的城市为 3,43,4，这两个城市与城市 22 的距离分别为 2,12,1，所以城市 44 离城市 22 最近，因此小B会走到城市44。到达城市 44 后，前面已没有可到达的城市，所以旅行结束。
如果从城市 22 出发，可以到达的城市为 3,43,4，这两个城市与城市 22 的距离分别为 2,12,1，由于城市 33 离城市 22 第二近，所以小 AA 会走到城市 33。到达城市 33 后，前面尚未旅行的城市为 44，所以城市 44 离城市 33 最近，但是如果要到达城市 44，则总路程为 2+3=5>32+3=5>3，所以小 BB 会直接在城市 33 结束旅行。
如果从城市 33 出发，可以到达的城市为 44，由于没有离城市 33 第二近的城市，因此旅行还未开始就结束了。
如果从城市 44 出发，没有可以到达的城市，因此旅行还未开始就结束了。
【样例2说明】
当 x=7x=7 时，如果从城市 11 出发，则路线为 1→2→3→8→91→2→3→8→9，小 AA 走的距离为 1+2=31+2=3，小 BB 走的距离为 1+1=21+1=2。（在城市 11 时，距离小 AA 最近的城市是 22 和 66，但是城市 22 的海拔更高，视为与城市 11 第二近的城市，所以小 AA 最终选择城市 22；走到99 后，小 AA 只有城市 1010 可以走，没有第二选择可以选，所以没法做出选择，结束旅行）
如果从城市 22 出发，则路线为 2→6→72→6→7，小 AA 和小 BB 走的距离分别为 2,42,4。
如果从城市 33 出发，则路线为 3→8→93→8→9，小 AA 和小 BB 走的距离分别为2,12,1。
如果从城市 44 出发，则路线为 4→6→74→6→7，小 AA 和小 BB 走的距离分别为 2,42,4。
如果从城市 55 出发，则路线为 5→7→85→7→8，小 AA 和小 BB 走的距离分别为 5,15,1。
如果从城市 66 出发，则路线为 6→8→96→8→9，小 AA 和小 BB 走的距离分别为5,15,1。
如果从城市 77 出发，则路线为 7→9→107→9→10，小 AA 和小 BB 走的距离分别为2,12,1。
如果从城市 88 出发，则路线为 8→108→10，小 AA 和小 BB 走的距离分别为2,02,0。
如果从城市 99 出发，则路线为 99，小 AA 和小 BB 走的距离分别为 0,00,0（旅行一开始就结束了）。
如果从城市 1010 出发，则路线为 1010，小 AA 和小 BB 走的距离分别为0,00,0。
从城市 22 或者城市 44 出发小 AA 行驶的路程总数与小 BB 行驶的路程总数的比值都最小，但是城市 22 的海拔更高，所以输出第一行为 22。
【数据范围与约定】
对于 30%30% 的数据，有1≤n≤20,1≤m≤201≤n≤20,1≤m≤20；
对于40%40% 的数据，有1≤n≤100,1≤m≤1001≤n≤100,1≤m≤100；
对于 50%50% 的数据，有1≤n≤100,1≤m≤10001≤n≤100,1≤m≤1000；
对于 70%70% 的数据，有1≤n≤1000,1≤m≤1041≤n≤1000,1≤m≤104；
对于 100%100% 的数据：1≤n,m≤1051≤n,m≤105，−109≤hi≤109−109≤hi≤109，1≤si≤n1≤si≤n，0≤xi≤1090≤xi≤109
数据保证 hihi 互不相同。
这个题目给我的感觉不是很好，我读懂后却没有一点头绪。。
（如果是在oi的时候，那我可能就st表或者线段树拿70分跑了，但是现在是acm。。没有骗分）
或者说我一开始的时候根本就没用去往dp的方向想。。好像缺了一个把我引导去想dp的引子
奇怪
好像知道了，这个第二问没有给我dp的感觉，但是这个第一问还是有感觉的
(最近写的题目dp特征都太明显了，突然换类型有点不适应。。）
主要是第一题是一个最优解。。
我知道了，因为第二问没有“我的选择”的体现，而是在询问我一个固定的值，这个其实更像是递推而不是dp，没有搜索不同情况的解的过程
这种类型的dp是要建立不同解之间的关系吗?
倍增。。
像是递推里面用的一个东西吧。。
主要的特征就是，当前的状态既是需要的答案，也是后续答案的一个跳板，那我们就可以不用对每一个i<=n都遍历一遍n，而是倍增的去求，就能够遍历完所有的位置了
（就是我们不需要每一个位置去更新后面所有其他位置的答案，就是这么简单）
我目前的理解就只有这个
对于这题的第一问，我们其实可以发现一个特点，就是其实a开的距离之和起始位置有关，和时间无关，这个的意思就是，我们可以合并两端长度，比如a开到c的长度可以是从a开到b，然后加上从b开到c的长度（虽然不一定）
这个就倍增计算了
这么看的话倍增的特征还是特别明显的，这其实接近一个递推而不是dp
我又想了想，其实应该说的是你第i天和第j天从同一个地点出发，最终的终点肯定是不会变的
所以这应该算是一个递推而不算是一个dp
这个题目。。其实应该先算第二问，第二问出来了第一问也就出来了
我先把做法和代码给搞了，再分析一下该怎么思考和这类题目的特点。
额，学到了一个双向链表求单项最大值次大值位置。。(st表也一样，可能复杂点吧)
我错了，应该是我的写法的问题，双向链表比st表写起来复杂
。。。（这个代码量快赶上我的手写平衡树了。。。。）
这么看的话倍增其实和二分的相似程度很高啊，都有一个类似搜索的过程，然后都是用单调性来快速前进，得到答案
复杂度很相似。。
好吧其实大多数时候不一样
这题我莫名其妙wa了。。只有大数据，调不了，没办法。。
其实感觉没有紫题难度，顶多蓝题
紫题的思维难度和巧妙的地方没有。。代码难度也没有那些状压的紫题难，唯一烦的也就是代码长度了。。我写了6kb，但是写的挺快的，因为没啥麻烦的
可以说是一个非常简单的状压优化dp，很模板
前面套了一个求最小值和次小值，其他没啥了
主要是让我学到了倍增运用的一个特点或者说是范围吧
其他的没啥了
附上我的80分代码。。。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read() {
char c=getchar();ll a=0,b=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
ll n,dist1[150001],dist2[150001],c[150001],f[17][150001][2],da[17][150001][2],db[17][150001][2];//2^i天，从j出发，k开车（0是a，1是b）
struct chain
{
ll next,last,v,id;
bool con;
}a[150001];
bool mycmp1(chain a,chain b)
{
return a.v<b.v;
}
bool mycmp2(chain a,chain b)
{
return a.id<b.id;
}
int main()
{
freopen("1.in","r",stdin);
freopen("2.out","w",stdout);
n=read();
for(ll i=1;i<=n;i++)
{
a[i].v=read();
a[i].id=i;
}
sort(a+1,a+1+n,mycmp1);
for(ll i=2;i<=n-1;i++)
{
a[i].last=a[i-1].id;
a[i].next=a[i+1].id;
}
a[1].last=0;
a[1].next=a[2].id;
a[n].last=a[n-1].id;
a[n].next=0;
a[0].v=1ll<<60;
a[n+1].v=1ll<<60;
sort(a+1,a+1+n,mycmp2);
for(ll i=1;i<=n;i++)
{
ll min1=1ll<<60,min2=1ll<<60,id1=0,id2=0;
ll j,k,cnt=0;
for(j=a[i].last,k=a[i].next;;j=a[j].last,k=a[k].next)
{
if(min1>abs(a[j].v-a[i].v))
{
min2=min1;
id2=id1;
min1=abs(a[i].v-a[j].v);
id1=a[j].id;
}
else
if(min1==abs(a[j].v-a[i].v))
{
min2=abs(a[j].v-a[i].v);
id2=a[j].id;
if(a[id2].v<a[id1].v)
{
swap(id1,id2);
swap(min1,min2);
}
}
else
if(min2>abs(a[j].v-a[i].v))
{
min2=abs(a[i].v-a[j].v);
id2=a[j].id;
}
else
if(min2==abs(a[j].v-a[i].v))
if(a[j].v<a[id2].v)
{
min2=abs(a[i].v-a[j].v);
id2=a[j].id;
}
if(min1>abs(a[k].v-a[i].v))
{
min2=min1;
id2=id1;
min1=abs(a[i].v-a[k].v);
id1=a[k].id;
}
else
if(min1==abs(a[k].v-a[i].v))
{
min2=abs(a[k].v-a[i].v);
id2=a[k].id;
if(a[id2].v<a[id1].v)
{
swap(id1,id2);
swap(min1,min2);
}
}
else
if(min2>abs(a[k].v-a[i].v))
{
min2=abs(a[i].v-a[k].v);
id2=a[k].id;
}
else
if(min2==abs(a[k].v-a[i].v))
if(a[k].v<a[id2].v)
{
min2=abs(a[i].v-a[k].v);
id2=a[k].id;
}
if(cnt==1)break;//两次内必出答案
cnt=1;
}
dist1[i]=id1;
dist2[i]=id2;
a[a[i].last].next=a[i].next;
a[a[i].next].last=a[i].last;
}//我服了，还是set简单。。 md写个这个东西给我整的汗流浃背。。。
for(ll i=1;i<=n-1;i++)
{
f[0][i][0]=dist2[i];
f[0][i][1]=dist1[i];
da[0][i][0]=abs(a[i].v-a[dist2[i]].v);
db[0][i][1]=abs(a[i].v-a[dist1[i]].v);
}
f[0][n-1][1]=dist1[n-1];
f[0][n][0]=f[0][n][1]=0;//边界情况
for(ll i=1;i<=double(log(n)/log(2));i++)
{
for(ll j=1;j<=n;j++)
{
if(i==1)
{
f[i][j][0]=f[0][f[i-1][j][0]][1];
f[i][j][1]=f[0][f[i-1][j][1]][0];
}
else
{
f[i][j][0]=f[i-1][f[i-1][j][0]][0];
f[i][j][1]=f[i-1][f[i-1][j][1]][1];//不存在的情况。。
}
}
}
for(ll i=1;i<=double(log(n)/log(2));i++)
{
for(ll j=1;j<=n;j++)
{
if(i==1)
{
da[i][j][0]=da[i-1][j][0]+da[i-1][f[i-1][j][0]][1];
da[i][j][1]=da[i-1][j][1]+da[i-1][f[i-1][j][1]][0];
}
else
{
da[i][j][0]=da[i-1][j][0]+da[i-1][f[i-1][j][0]][0];
da[i][j][1]=da[i-1][j][1]+da[i-1][f[i-1][j][1]][1];
}
}
}
for(ll i=1;i<=double(log(n)/log(2));i++)
{
for(ll j=1;j<=n;j++)
{
if(i==1)
{
db[i][j][0]=db[i-1][j][0]+db[i-1][f[i-1][j][0]][1];
db[i][j][1]=db[i-1][j][1]+db[i-1][f[i-1][j][1]][0];
}
else
{
db[i][j][0]=db[i-1][j][0]+db[i-1][f[i-1][j][0]][0];
db[i][j][1]=db[i-1][j][1]+db[i-1][f[i-1][j][1]][1];
}
}
}
ll x0=read(),m=read(),min1=0,min2=0,id=0;
ll ned1,ned2;
for(ll now=1;now<=n;now++)
{
ll si=now,xi=x0,ans1=0,ans2=0;
for(ll i=(log(n)/log(2));i>=0;i--)
{
if(i>1)//看看是谁在开车车
{
if(f[i][si][0]!=0&&ans1+ans2+da[i][si][0]+db[i][si][0]<=xi)//没走到了边界
{
ans1+=da[i][si][0];
ans2+=db[i][si][0];
si=f[i][si][0];
}
}
else
{
if(f[i][si][0]!=0&&ans1+ans2+da[i][si][0]+db[i][si][0]<=xi)
{
ans1+=da[i][si][0];
ans2+=db[i][si][0];
si=f[i][si][0];
}
}
}
if(f[0][si][1]!=0&&ans1+ans2+da[0][si][0]+db[0][si][0]<=xi)
{
ans2+=db[0][si][1];
si=f[0][si][1];
}
if(ans2!=0&&min2!=0)
{
if(double(double(ans1)/double(ans2))<double(double(min1)/double(min2)))
{
min1=ans1;
min2=ans2;
id=now;
}
}
else
{
if(min2==0)
{
min1=ans1;
min2=ans2;
id=now;
}
}
if(now==30)
{
ned1=ans1,ned2=ans2;
}
}
cout<<id<<endl;
// cout<<min1<<' '<<min2<<' '<<ned1<<' '<<ned2<<endl;
// double cn1=double(min1)/double(min2),cn2=double(ned1)/double(ned2);
// cout<<cn1<<' '<<cn2<<endl;
for(ll T=1;T<=m;T++)
{
ll si=read(),xi=read(),ans1=0,ans2=0;
for(ll i=(double(log(n)/log(2)));i>=0;i--)
{
if(i>1)//看看是谁在开车车
{
if(f[i][si][0]!=0&&ans1+ans2+da[i][si][0]+db[i][si][0]<=xi)//没走到了边界
{
ans1+=da[i][si][0];
ans2+=db[i][si][0];
si=f[i][si][0];
}
}
else
{
if(f[i][si][0]!=0&&ans1+ans2+da[i][si][0]+db[i][si][0]<=xi)
{
ans1+=da[i][si][0];
ans2+=db[i][si][0];
si=f[i][si][0];
}
}
}
if(f[0][si][1]!=0&&ans1+ans2+da[0][si][0]+db[0][si][0]<=xi)
{
ans2+=db[0][si][1];
si=f[0][si][1];
}
cout<<ans1<<' '<<ans2<<endl;
}
return 0;
}
/*
10
4 5 6 1 2 3 7 8 9 10
7
1
7 7
2 1
*/
然后就要弄其他的倍增了。。
感觉就这题根本没让我认识到倍增优化的难度。。