TOJ4101.Guess Game(TOJ means Tianjin University Online Judge)（dp的思想，但这道题目是假dp）

题意：你要从[1,n]这个n个数中猜出来规定的某个数，现在这个数未知，问你在最糟糕的情况下（但是你采用了最优的策略），你要猜多少次才能猜出这个数。现在有两种条件：

第一种：当你猜的数比指定的那个数小的时候，系统会提示你small;

第二种：当你猜的数比指定的那个数大的时候，系统会提示你wrong，但是从这以后不论你猜的数比指定数大或小，系统将永远提示你wrong。

在这里最糟糕情况可以理解为这个人很倒霉，命运总是让他多猜。

分析：

数列：1，2，3，4，....，k，....，n

比如说你猜了数字k，那么现在有两种情况：

α.你猜的数字比指定的数字大了，由于你很倒霉，所以你得一个个地往小里猜，此时最糟糕的情况是指定数字是1，那么你要猜k - 1次；

β.你猜的数字比指定的数字小了，那么相当于又开始了一个规模为n-k的游戏；

现在定义dp[i]---->在最糟糕的情况下，从规模为i的数列中猜数，最少要猜多少次。

那么我们应该怎么制定自己的策略呢？由于你很倒霉，那么命运一定会让你进入两种情况中多的那一种。那么好，我就让两种情况要猜的数尽量相等，这样就是最优的策略。

dp[i] = min{max(k-1,dp[i-k])+1；

memset(dp,F,sizeof(dp));

    dp[] = ,dp[] = ,dp[] = ,dp[] = ;

    for(int i = ;i <= ;++i){

        for(int j = ;j <= i;++j){

            dp[i] = min(dp[i],max(dp[i - j],j - ) + );

        }

    }

然而n<= 10⁹，这样的时间复杂度是O(n²)，空间复杂度是O(n)。

即爆时间又爆空间。

这就是为啥说这是个假dp了，然而让人惊喜的是，这道题目的得数有规律：

从1到n对应的得数分别是：1个1，2个2，3个3，4个4......

那这个就相当于解一个不等式了，(X²+X)/2 ≥ n，由于在定义域上单调，这里用二分搜索即可：

AC代码：

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

//#define LOCAL

using namespace std;

int calculate(int x)

{

    return (x * x + x)>>;

}

int main()

{

    //#ifdef LOCAL

      //freopen("TOJ4101.txt","r",stdin);

      //freopen("TOJ4101out.txt","w",stdout);

    //#endif

    int T;

    scanf("%d",&T);

    while(T--){

        int n;

        scanf("%d",&n);

        int rht = ,lft = ,mid = (lft + rht)>>,temp;

        while(rht != lft){

            temp = calculate(mid);

            if(temp < n) lft = mid + ;

            else if(temp == n){

                lft = mid;

                break;

            }

            else if(temp > n){

                rht = mid;

            }

            mid = (lft + rht)>>;

            //printf("left is %d and right is %d\n",lft,rht);

        }

        printf("%d\n",lft);

    }

    return ;

}

巴特西

TOJ4101.Guess Game(TOJ means Tianjin University Online Judge)（dp的思想，但这道题目是假dp）

最新文章

热门文章