Ural 1223 & POJ 3783 鷹蛋問題

     昨晚隊内練習賽做了Greater New York Regional 2009套題...水一套..不過還有有道很經典的問題...鷹蛋問題...IOI2004年的一論文就對這個問題有過深入探讨...比賽的時候我隻想到了個大概...

     我的思路和論文中的方法二差不多...狀态的表示dp[k][p]代表在确定層數為k時用p個球所需确定鷹蛋承受能力的最小次數...也就是輸入輸出的東西了...我覺得這種狀态時最為直覺的...在更新時可以用二分..那麼時間複雜度為O(n^m*logn)..有0<n,m<=1000...可以接受....

     直覺的例子...首先初值dp[k][1]=k...(0<k<=1000) 顯而易見...如果要更新出dp[10][2]...

          最優方案: 将第一個蛋在4層扔一次..若蛋碎..問題轉化為dp[3][1].. 若沒碎... 再将第一個蛋在7層扔一次..若此時但碎..問題轉化為dp[[2][1]...若第一個蛋還沒碎..再将第一個蛋在9層扔一次..若蛋碎..問題轉化為dp[1][1]..若沒碎..問題轉化為dp[1][1]...可見由于第一個蛋的碎與沒碎..将情況分類成好些...而dp[3][1]+1是最多的..為4..是以dp[10][2]=4..

          那為何在第4層失敗後...第二次是扔第7層..因為知道dp[3][1]=3..那麼要維持最多時dp[3][1]+1=4次..那麼就要保證第一個蛋扔兩次後第二個蛋隻能扔2次...若兩次的距離為2..dp[2][1]=2...2+2=4..那麼可行...4+1+2=7..同理...7+1+1=9位第二次扔1号蛋沒碎後要選擇的層數..因為能保證dp[1][1]=1,1+3=4..

          如何确定第一次是第4層?..由于第一次扔在哪就能直接确定後面扔在哪..且第一次扔的高度與這種方案确定的次數是同單調的...如dp[100][2]一定不會大于dp[200][2]...靠2分枚舉...因為如果第一次扔第k層ok...那麼第一次扔k-1也一定是ok的..

     再譬如要更新dp[100][3]...二分l=-1,r=100,第一次的mid=50...

         嘗試...将第一個蛋先扔在50..那麼就要保證往後的次數為dp[49][2]+1...是以第一個蛋若再50層沒碎..第二次應該到96層...為何呢..因為第一個蛋較前種情況會多扔一次..那後兩個蛋隻能少扔一次...要保證兩次的間隙層數=dp[49][2]-1.而dp[45][2]=dp[49][2]-1..且45是滿足條件最大的(dp[46][2]=dp[47][2]=dp[48][2]=dp[49][2])...如此下去..到第一個蛋扔3次時..所能覆寫的範圍超出100了...得出3個蛋第一次扔在50層一定能測試出100層之内的鷹蛋極限承受層數...那麼在l=-1,r=50隻能繼續找答案...

      這樣寫還是會逾時..小優化..若發現蛋不斷增加時..次數并沒有減少..就沒必要還來找了..但不能出現前後相同就跳出來直接指派..我就這裡WA了好幾次...我AC的程式是判斷當球增加時連續5個的值相同..則跳出直接指派...

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000000
#define pi acos(-1)
using namespace std;   
int T,t,n,m,dp[1005][1005],f[1005];
int main()
{  
     int i,j,l,r,mid,k,x,h;
     memset(dp,0,sizeof(dp));
     for (i=0;i<=1000;i++) dp[i][1]=i;
     for (i=1;i<=1000;i++)
     {  
           memset(f,0,sizeof(f));
           for (j=2;j<=1000;j++)
           {
                  l=0;  r=i; 
                  while (r-l>1)
                  { 
                         mid=(r+l)/2;
                         k=0;
                         x=mid;
                         while (k<i && x>0)
                         {
                               h=dp[x-1][j-1];
                               k+=x;
                               while (x>0 && dp[x-1][j-1]==h) x--;
                         }
                         if (k>=i) r=mid;
                            else l=mid; 
                  }
                  k=dp[r-1][j-1]+1; 
                  f[k]++;
                  if (f[k]>5) break;
                  dp[i][j]=k;
           }
           for (;j<=1000;j++) dp[i][j]=k;
     } 
     /*
     scanf("%d",&T);
     for (t=1;t<=T;t++)
     {
            scanf("%d%d%d",&m,&m,&n);
            printf("%d %d\n",t,dp[n][m]);
     }  POJ OUTPUT*/
   /*  while (~scanf("%d%d",&m,&n))
     {
            if (!n && !m ) break; 
            printf("%d\n",dp[n][m]);
     } URAL OUTPUT*/
     return 0;
}