POJ3783 Balls DP动态规划

Categories: 数据结构和算法
Tags:
Comments: No Comments
Published on: 2011 年 03 月 21 日

/* 
    动态规划DP: 
        状态转移方程:DP[i][j]=DP[i][j-1]+DP[i-1][j-1]+1; 
        其中i代表小球个数,j代表可扔次数。DP[][]表示该状态下可测出的楼层数。 
        由状态转移方程可清晰看出,DP[i][j]在第某层楼X扔下一个小球, 
        如果该球破碎,那么其结果是DP[i-1][j-1]的情况(即少一个球少一次机会); 
        如果该球未破碎,那么其结果是DP[i][j-1]的情况(即球不少,但少一次机会); 
        所以DP[i][j]能测的楼层数为DP[i][j-1]+DP[i-1][j-1]+1的和。 
*/  
#include<iostream>    
#include<algorithm>    
using namespace std;    
const int MAXBall=55,MAXFloor=1010;    
int DP[MAXBall][MAXFloor];    
int main()    
{    
    //freopen("1.txt","r",stdin);  
    for(int i=0;i<=1000;i++) DP[1][i]=i;    
    for(int i=2;i<=50;i++)    
        for(int j=1;j<=1000;j++)    
        {    
            if(i>j) DP[i][j]=DP[j][j];     
            else DP[i][j]=DP[i-1][j-1]+DP[i][j-1]+1;   
            //以免其中数据过大,数据规模最大为1000,所以封上界。  
            if(DP[i][j]>1010) DP[i][j]=1010;    
        }    
        int n,th,ball,floor;    
        cin>>n;    
        while(n--)    
        {    
            cin>>th>>ball>>floor;    
            cout<<th<<" "<<lower_bound(DP[ball],DP[ball]+1000,floor)-DP[ball]<<endl;    
        }    
}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日