首页 > 代码库 > hdu--4576--概率dp<见过最简单的概率dp>
hdu--4576--概率dp<见过最简单的概率dp>
看到 expected possibility 一下子 又觉得是概率dp了..
这题 也的确是了
但做的狠无语啊 尝试了2种 一个是TLE 一个是AC 但也要花掉了3000多ms。。
而且 我也觉得这两种 区别不大啊 思想是一样的 就是处理上有点区别..
应该是第二种TLE的故意被卡了时间吧 my guess
这题的话 思路很简单 就是一层一层的递推下来 并且这一层的状态只与上一层有关~
其实 每次可以选择走的方案数就是： 2^1 --> 2^2 --> 2^3 --> ......->2^m
不用管2^m的值会很大 因为一共只有200个格子 n<=200 那么我只要遍历n就够了
求大神 帮我纠错 第一份代码 =_=
刚开始用了set来处理 严重tle 真烦..
1 #include <iostream> 2 #include <iomanip> 3 using namespace std; 4 5 const int size = 210; 6 double dp[2][size]; 7 8 int main( ) 9 {10 cin.sync_with_stdio(false);11 int n , m , L , R , k , x , y , w;12 double ans;13 while( cin >> n >> m >> L >> R && ( n || m || L || R ) )14 {15 k = 0;16 for( int i = 0 ; i<=n ; i++ )17 {18 dp[0][i] = dp[1][i] = 0.0;19 }20 for( int i = 0 ; i<m ; i++ )21 {22 cin >> w;23 if( !i )24 {25 x = (1+w-1)%n + 1;26 y = (1+n-w)%n;27 y = (y==0) ? n : y;28 dp[k][x] = 0.5;29 dp[k][y] = 0.5;30 //cout << x << " " << y << endl;31 }32 else33 {34 for( int j = 1 ; j<=n ; j++ )35 {36 if( dp[k][j] )37 {38 x = (j+w-1)%n+1;39 y = (j+n-w)%n;40 y = (y==0) ? n : y;41 dp[!k][x] += dp[k][j] * 0.5;42 dp[!k][y] += dp[k][j] * 0.5;43 //cout << x << " " << y << endl;44 }45 dp[k][j] = 0;46 }47 k = !k;48 }49 }50 ans = 0;51 for( int i = L ; i<=R ; i++ )52 {53 ans += dp[(m+1)&1 ][i];54 //cout << dp[(m+1)&1][i] << endl;55 }56 cout << setiosflags(ios::fixed);57 cout << setprecision(4) << ans << endl;58 }59 return 0;60 }61 /*62 4 3 1 263 164 265 366 */
1 #include <iostream> 2 #include <iomanip> 3 using namespace std; 4 5 const int size = 210; 6 double dp[2][size]; 7 8 int main( ) 9 {10 cin.sync_with_stdio(false);11 int n , m , L , R , k , x , y , w;12 double ans;13 while( cin >> n >> m >> L >> R && ( n || m || L || R ) )14 {15 k = 1;16 for( int i = 0 ; i<=n ; i++ )17 {18 dp[0][i] = dp[1][i] = 0.0;19 }20 dp[0][0] = 1.0;21 for( int i = 0 ; i<m ; i++ )22 {23 cin >> w;24 for( int j = 0 ; j<n ; j++ )25 {26 if( dp[!k][j] )27 {28 dp[k][(j+w)%n] += dp[!k][j] * 0.5;29 dp[k][(j-w+n)%n] += dp[!k][j] * 0.5;30 }31 dp[!k][j] = 0;32 }33 k = !k;34 }35 ans = 0;36 for( int i = L-1 ; i<=R-1 ; i++ )37 {38 ans += dp[ m&1 ][i];39 }40 cout << setiosflags(ios::fixed);41 cout << setprecision(4) << ans << endl;42 }43 return 0;44 }
today:
昨天
你说
明天
岁就就是如此这般地被我们蹉跎了
hdu--4576--概率dp<见过最简单的概率dp>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。