HDU 5981 Guess the number

原题链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5981

题目大意是：

A 在区间[a,b]上猜一个数字， B 猜测A猜测的数字。如果 B 猜测小了A会告诉他,一旦 B 猜测的大了。A不会再告诉 B ，直到B猜到这个数字为止 游戏结束。

问，在B每次做决定后。情况最差时。最少猜测多少次。

<script type="math/tex; mode=display" id="MathJax-Element-318"></script>

那么猜测次数明显和 a,b 无关。而与 b−a+1 即区间长度有关。

对于长度为 L 的区间。定义最少猜测次数为

dp[L]

显然：

dp[L]=mink=1L(max( k−1, dp[L−k] ))

特别的 dp[0]=0 ; dp[1]=1 ; dp[2]=2 。

显然： dp[L]≤dp[L+1]dp[L+1]−dp[L]≤1

则函数 dp[L−x] 的值域是 [ 0,dp[L]] 所有整数。

则：函数 f(x)=x−1 与函数 g(x)=dp[L−x] 可能在交点。

并不一定存在交点。（这点想清楚有利于下面实现优化）

因为。 f(x) 是单调不降。 g(x) 单调不增。

随着 L 的改变,g(x)图像向右平移。 f(x) 不动。所以最小值时的最大的k有可能增加。但不会减少。

维护这样一个 k 。使得dp[L−k]≤k−1的最小的 k (为什么这样。可以画图细细体会。

即如下代码：

while(dp[L-k]>k-1)k++

结束循环时的k即为最佳。(当然然最佳选择不唯一）

那么与 dp[L−k′]=k−1 且 dp[L−k′]≥k′ 相等的所有 k′ 可以选择。

如果 dp[L−k]<k−1 。由递推关系可得。 dp[L−k] 也可以用。

这些都可以选择的方案用来维护方案数量。

记为 S[]

其中 S[0]=0 ; S[1]=1 ; S[2]=2。

#include <algorithm>
#include <string.h>
#include <map>
#define MAXN 5000010
using namespace std;
typedef long long LL;
const int P=100000073;
struct Bf
{
int A[MAXN];
Bf()
{
for(int i=0;i<MAXN;i++) A[i]=i;
}
int find(int a)
{
if(a==A[a])return a;
return A[a]=find(A[a]);
}
}B;
int dp[MAXN];
int S[MAXN];
int main ()
{
dp[1]=S[1]=1;
dp[2]=2;
S[2]=3;
int k=2;
for(int x=3;x<MAXN;x++)
{
while(dp[x-k]>k-1)k++;
dp[x]=k;
int b;
if(dp[x-k]==k-1)
b=B.find(x-k);
else
b=B.find(x-k+1);
S[x]=(S[x-1]+S[b]-S[x-k-1]+P)%P;
if(dp[x]==dp[x-1])B.A[x-1]=x;
}
int a,b;
while(scanf("%d %d",&a,&b)==2)
{
int x=b-a+1;
printf("%d %dn",dp[x],(S[x]-S[x-1]+P)%P);
}
return 0;
}

最后

以上就是过时香氛为你收集整理的HDU 5981 Guess the numberHDU 5981 Guess the number的全部内容，希望文章能够帮你解决HDU 5981 Guess the numberHDU 5981 Guess the number所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。