poj1243（经典dp）-白红宇

poj1243（经典dp）

阅读量：6760 次

发布时间：2019-06-26

本文共 1449 字，大约阅读时间需要 4 分钟。

题目链接：

题意：让你猜一个物品的价格，猜低了或者猜高了都会提示你。G,L，表示你有G次机会猜一个数，如果猜错了，G会减少1次，如果你的错误是应该是猜高了，那么L也会少一次（猜低了L不会少）。如果G次机会都用完了，则输；若G次机会还有剩余，而L次机会用完了，这时再猜一个数，若猜高了，那么也输了。让你确定一个数字N，以保证在G,L的条件下，你一定能猜到[1,N]以内的任何一个数

1.如果L等于0，也就是说你在猜的过程中，绝对不能猜高，所以你只能从1开始猜，并依次为2,3,4……最大能猜到的数是G，所以N=G,这样才能保证你一定能猜到其中的任何一个数

2.L>G，这是个迷惑的情况，其实L比G大是没意义的，因为无论猜高了猜低了G都会减少，所以G一定先为0，G L等价于G G

3.L=G，这个情况和上面的情况是一样的，这样的猜测是不需要考虑什么猜高猜低的，因为G也一定是先变为0，那么像G G这种情况能猜的范围是多少呢？就是N=(2^G)-1，这是由二分查找的性质可以得知的

4.L<G，这个才是真正需要DP的。这样考虑策略，dp[i][j]表示还有i次机会，j次猜高的机会情况下能猜测的最大长度（即N）

我们猜测一个数字x

如果猜低，剩下i-1次机会，j次猜高的机会，那么正确的数字在[x+1, INF)范围内，假设我们已经知道了dp[i-1][j]，那么这个数字只能出现在[x+1 , dp[i-1][j]+x]范围内，才能保证我们一定猜到它

如果猜高，剩下i-1次机会，j-1次猜高的机会，那么正确的数字在[1,x-1]范围内，假设我们已经知道了dp[i-1][j-1]，那么为了最大化，必定要使x=dp[i-1][j-1]+1(若不选x刚好大于dp[i-1][j-1],太小会使范围重复，太大则不能在规则内猜得到)

如果猜对了，那么就赢了，即总范围+1

所以在（i，j）的情况下我们能猜的最大范围就是 dp[i][j]=dp[i-1][j-1]+1+dp[i-1][j]；

例如：3 1先选择点3，假设目标低于3，还有两次机会必定能猜到。假设目标高于3，再选择5，假设目标低于5，还有一次机会刚好猜4，若高于5，刚好猜6.所以总范围为6.即dp[3][1]=dp[2][0]+1(点3本身)+dp[2][1].

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 50010using namespace std;int dp[50][50];void init(){ for(int i=1;i<=30;i++) { dp[i][0]=i;dp[i][i]=(1<
                
                 0) { if(n+m==0)break; if(n

View Code

转载于:https://www.cnblogs.com/lienus/p/4161487.html

你可能感兴趣的文章