#交互，dp#洛谷 7998 [WFOI - 01] 猜数（guess）

题目传送门

---

分析

首先要搞清楚，交互库的自适应会让区间长度尽可能增大（答案自适应）

也就是说，如果现在区间为 \([l,r]\)，你选取的区间为 \([l',r']\)，

那么交互库会让你的区间变成 \([l,r'-1]\) 和 \([l'+1,r]\) 中区间更长的那一个，不妨枚举这个长度

设 \(dp[i]\) 表示区间长度为 \(i\) 时的最小询问总代价，也就是要决定下一步让交互库缩短到的区间长度，设其为 \(j\)

那么就要保证 \(1\leq i-j+1\leq j\leq n\)，且此时询问代价为 \(\frac{1}{j-(i-j+1)+1}=\frac{1}{2j-i}\)

那么 \(dp[i]=\min_{\lceil\frac{i+1}{2}\rceil\leq j\leq i}\{dp[j-1]+\frac{1}{2j-i}\}\)

按照最优决策点决策就能将总代价卡在能过的范围内，且 \(j\) 的选取可以将范围缩小到 \(p[i-1]\pm \Delta\)，

由于并不需要非常精确地求出最小的 dp 值，所以这样预处理的复杂度就是 \(O(n\Delta)\) 的

---

代码

#include <iostream>
using namespace std;
const int N=100011;
double dp[N]; int n,pos[N];
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n,pos[1]=1;for (int i=2;i<=n;++i){dp[i]=i;int L=max((i+2)>>1,pos[i-1]-800);int R=min(i,pos[i-1]+800);for (int j=L;j<=R;++j){double t=dp[j-1]+1.0/(j-(i-j+1)+1);if (dp[i]>t) dp[i]=t,pos[i]=j;}}int l=1,r=n;while (l<r){int lmid=r-pos[r-l+1]+1,rmid=l+pos[r-l+1]-1,x,opt;cout<<"? "<<lmid<<' '<<rmid<<'\n',cout.flush();cin>>x>>opt;switch (opt){case 0:{l=x+1;break;}case 1:{cout<<"! "<<x<<'\n';cout.flush();l=r=x;break;}case 2:{r=x-1;break;}}}cout<<"! "<<l<<'\n';cout.flush();return 0;
}