国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > zoj 1503 - One Person "The Price is Right"

zoj 1503 - One Person "The Price is Right"

来源:程序员人生   发布时间:2014-10-10 08:00:01 阅读次数:2215次

题目:有一个数字让你猜,你有k次机会,并且有k个保险如果猜的低了会高度你低了,

            高了会告诉你高了,并且失去一k保险(k=0时猜高了就会失败),现在问你能猜的数字范围。

分析:dp,二维动态规划。按保险k和猜的机会n递增的方向dp。

            状态:f(G,L)为有G次猜的机会,L个保险时确定的数字范围(1~N);

            转移方程:F(G,L)= G(G-1,L)+ 1 + F(G-1,L-1){ 猜低 + 猜中 + 猜高 };

            边界条件:如果没有失败机会的话,只能从1开始向后猜;

说明:(2011-10-03 16:32)。

#include <iostream> #include <cstdlib> using namespace std; long long F[ 31 ][ 31 ]; int main() { for ( long long i = 0 ; i <= 30 ; ++ i ) F[ i ][ 0 ] = i; for ( int i = 0 ; i <= 30 ; ++ i ) F[ 0 ][ i ] = 0L; for ( int i = 1 ; i <= 30 ; ++ i ) for ( int j = 1 ; j <= 30 ; ++ j ) F[ i ][ j ] = F[ i-1 ][ j ]+F[ i-1 ][ j-1 ]+1; int G,L,C = 1; while ( cin >> G >> L && ( G || L ) ) cout << "Case " << C++ << ": " << F[ G ][ L ] << endl; return 0; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生