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

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

2024-09-26 17:43:39   214人阅读

题意：你要从[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[0] = 0,dp[1] = 1,dp[2] = 2,dp[3] = 2;
    for(int i = 4;i <= 10000;++i){
        for(int j = 1;j <= i;++j){
            dp[i] = min(dp[i],max(dp[i - j],j - 1) + 1);
        }
    }

 

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

即爆时间又爆空间。

 

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

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

那这个就相当于解一个不等式了，(X2+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)>>1;
}
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 = 10000,lft = 1,mid = (lft + rht)>>1,temp;
        while(rht != lft){
            temp = calculate(mid);
            if(temp < n) lft = mid + 1;
            else if(temp == n){
                lft = mid;
                break;
            }
            else if(temp > n){
                rht = mid;
            }
            mid = (lft + rht)>>1;
            //printf("left is %d and right is %d\n",lft,rht);
        }
        printf("%d\n",lft);
    }
    return 0;
}

 

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


联系
我们