【HDOJ5981】Guess the number（DP）

题意：A和B玩一个游戏：A在[L,R]之间随机选取一个数X，之后由B来猜这个数，

如果猜的数比X小，则A就告诉B你猜的数小了，

如果猜的数等于X则游戏结束，

如果猜的数大于X，则在这之后A只会回答B是否猜对了，而不会告诉B是否猜小了。

问:在最坏的情况下，B猜到X时最少需要猜多少次，并输出方案数对100000073取模

L,R<=5e6

思路：少了蛋数量的鹰蛋……

f[i]表示长度为i的区间需要的询问次数

p[i]表示至少需要i次询问的最短区间长度

a[i]表示区间长度为i的最优选择方案数

i可以由[i-f[i],p[f[i]]-1]转移而来

i-f[i]是还剩f[i]次机会，每次选择猜的数+1

p[f[i]]-1是需要测试f[i]-1次的最大区间长度

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<bitset>
 7 typedef long long ll;
 8 using namespace std;
 9 #define N   5100000
10 #define oo  10000000
11 #define MOD 100000073
12 
13 int f[N],p[N],a[N],s[N];
14 
15 int main()
16 { 
17     for(int i=1;i*(i+1)/2<N;i++)
18      for(int j=i*(i-1)/2+1;j<=i*(i+1)/2;j++) f[j]=i;
19     for(int i=1;i*(i-1)/2+1<N;i++) p[i]=i*(i-1)/2+1;
20     a[0]=a[1]=1;
21     a[2]=2;
22     s[1]=1; s[2]=3;
23     for(int i=3;i<N;i++)
24     {
25         int x=i-f[i];
26         int y=p[f[i]]-1;
27         a[i]=(s[y]-s[x-1]+MOD)%MOD;
28         s[i]=(s[i-1]+a[i])%MOD;
29     }
30     int x,y;
31     while(scanf("%d%d",&x,&y)!=EOF) printf("%d %d
",f[y-x+1],a[y-x+1]);
32     return 0;
33 }
34