首页 > 代码库 > hdu--4487--dp
hdu--4487--dp
dp是最有意思的。。 因为它永远没有固定的套路。。
最无聊的就是那些模板题了。。
这题 我被坑了。。 题意读错了。。 这边问的是A more interesting question is what is the expected rightmost position you will attain during the walk.
就是说 我们在每一次的走路过程中 所能达到的最右边的位置 我起初看成 走完n步以后 可以达到的最右边的位置= =
这边 是个很明显的 线性期望dp
一共就2个状态转移 对于dp[x,y,z] 走到了第x步 当前的位置是y 此时在这x步的过程中到底的最右边的距离是z
那么y与z一共就有3个大小关系了
y<z
dp[x&1][y][z] = dp[(x-1)&1][y+1][z] * L + dp[(x-1)&1][y][z] * M + dp[(x-1)&1][y-1][z] * R;
首先你要明确 dp[x,y,z]我是由dp[x-1,u,v]这个状态转移过来的 那么因为最多走一步 所以那就保证了即使我在u处向前走了一步 也不能超过v 最多可能等于v
y==z
dp[x&1][y][z] = dp[(x-1)&1][y-1][z-1] * R + dp[(x-1)&1][y][z] * M + dp[(x-1)&1][y-1][z] * R;
这时候就是说可能 我是第一次到达了z这个位置 或者我上一步就停在了z这个位置 或者是 我上上一步到达了z 但是上一步往左走了 这一步又往右走了 就还是最远距离是z
y<z
因为我现在都已经处在了 y 这个位置 那么离右边的最远距离z肯定是起码等于y啊<左边就拿原点处理>
至于 这个滚动数组 优化与否 没什么关系 数据很小 才100
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int n; 7 double L , R , M; 8 const int size = 105; 9 double dp[2][size*2][size*2];//dp[i,j,k]走到第i步的时候 走到了j这个位置 此时到达最右边的距离是k10 11 void init( )12 {13 memset( dp , 0 , sizeof(dp) );14 dp[0][size][size] = 1;15 }16 17 void solve( )18 {19 for( int i = 1 ; i<=n ; i++ )20 {21 for( int j = size-i ; i<=size+i ; j++ )22 {23 for( int k = max(j,size) ; k<=size+i ; k++ )24 {25 if( j==k )//第一次走到j这个位置 原地走 走到K之后 往回走了 现在再重新往前走26 {27 dp[i&1][j][k] = dp[(i-1)&1][j-1][k-1] * R + dp[(i-1)&1][j][k] * M + dp[(i-1)&1][j-1][k] * R;28 }29 else// k > j的情况30 {31 dp[i&1][j][k] = dp[(i-1)&1][j+1][k] * L + dp[(i-1)&1][j][k] * M + dp[(i-1)&1][j-1][k] * R;32 }33 }34 }35 }36 }37 38 int main()39 {40 int t , m;41 double ans;42 scanf( "%d",&t );43 while( t-- )44 {45 init( );46 scanf( "%d %d %lf %lf",&m,&n,&L,&R );47 M = 1 - L - R;48 solve( ); 49 ans = 0;50 for( int j = size - n ; j<=size+n ; j++ )51 {52 for( int k = size ; k<=size+n ; k++ )53 {54 ans += dp[n&1][j][k] * (k-size);55 }56 }57 printf( "%.4lf\n",ans );58 }59 return 0;60 }
hdu--4487--dp