期望dp哎,虽然以前也写过,但是不系统..虽然看到还是很迷茫的.
题目描述:

有一个游戏平板上面有n×m个格子，一开始每个格子都是关闭的，每个格子里面都有一个标记
已知每种标记恰好出现两次，也就是一共有n*m/2种标记
规定一次移动为依次(one by one不是同时)打开一对格子查看里面的标记，如果标记不一样，格子会自动关闭，但是你的记忆是超强了，看过了就不会忘，如果标记是一样的，格子从此就一直保持打开状态，当所有格子都打开时游戏结束
请算出游戏结束的最少期望步数

首先设dp[i][j]表示i个打开了,j个没打开的期望.然后就是转移了.

dp是由已知向未知转移的.那么,我们怎么转移呢?众所周知转移是凭借两个for
而转移的for是根据dp方程来的,所以我们来列一下dp方程.
好,我们肯定是要开箱子了,即dp[i][j]..
dp[i][j]<-怎么转移..
我们需要开两个箱子,开出来的两个箱子有4种情况..
第一种,我打开的这两张,我第一张之前翻开过,那么我下一张肯定是翻我之前的那张.
显然,我翻到这种的可能性是p=i/j.然后这样dp[i][j]=(dp[i-1][j-1]+1)*p.
第二种,我打开的这两张,第一张无对应,然后开第二张,1,2对应.
在i+j中翻一张牌,第一张不对应的可能性是1-p,然后1,2对应的可能性是a=1/(j-1).因为一定有两张对应,这样的dp就是.
dp[i][j]+=(1-p)*(a*(dp[i][j-2]+1)).//注意i记录打开了但是没被消除的.
第三种,我打开的两张,第一张无对应,然后开第二张,1,2不对应,且2与已知无对应.
第一张无对应就是(1-p),第二张和第一张和已知不对应的概率是b=((j-1)-1-i)/(j-1)=(j-2-i)/(j-1).
dp[i][j]+=(1-p)*(b*(dp[i+2][j-2]+1)).
第四种,我打开的两张,第一张无对应,然后开第二张,1,2不对应,且2与已知对应.
第一张无对应就是(1-p),第二张和第一张不对应但和已知对应的概率c=1-a-b.
dp[i][j]+=(1-p)*(c*(dp[i][j-2]+2)).
观察i,j的大小,j放第一维,i放第二维是可以的.因为i+2>i,不可能把i放第一维的.

代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=2505;
double dp[N][N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    n*=m;
    for(int j=0;j<=n;j++)
    {
        for(int i=0;i<=n;i++)
        {
            if(i+j>n||(j-i)%2||i>j) continue;//越界不合法的删除
            double p=(double)i/(double)j;
            if(i>0&&j>0) dp[i][j]=(dp[i-1][j-1]+1.0)*p;
            if(j>1)
            {
                double a=1.0/(double)(j-1.0);
                double b=(double)(j-2-i)/(double)(j-1);
                double c=1.0-a-b;
                dp[i][j]+=(1.0-p)*(a*(dp[i][j-2]+1.0));
                dp[i][j]+=(1.0-p)*(b*(dp[i+2][j-2]+1.0));
                dp[i][j]+=(1.0-p)*(c*(dp[i][j-2]+2.0));
            }
        }
    }
    printf("%.15f\n",dp[0][n]);
    return 0;
}