51nod 1450 闯关游戏——期望dp

题目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1450

想了半天，不知道不能走的状态（即最后不足m个的状态）怎么办。去吃晚饭的路上想到那种也是转移到 f[ i ][ j ] 自己，因为意义是需要再来一次，状态没有前进。

想出那个之前稍微看了点题解，不过只看到需要按 y 排序。若非此自己可能还想不到要排序。还对拍验证了一下，确实有差异。

把 y 大的排在前面，x 值大是第二关键字。之所以排在前面，是因为前面的影响更大（是倒着推的，所以排在后面，为了先算上），就想搜索的时候把分叉少的排在前面一样。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define db double

using namespace std;

const int N=; const db INF=0x3f3f3f3f;

int n,m;

db f[N][N<<];

struct Node{

  db x,y,z;

}a[N];

bool cmp(Node u,Node v){return u.y==v.y?u.x<v.x:u.y<v.y;}

int rdn()

{

  int ret=,fx=; char ch=getchar();

  while(ch>''||ch<''){ if(ch=='-') fx=-; ch=getchar();}

  while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return ret;

}

int main()

{

  //  freopen("51nod1450-data.in","r",stdin);

  //  freopen("51nod1450-bl.out","w",stdout);

  n=rdn(); m=rdn();

  for(int i=;i<=n;i++)

    a[i].x=(db)rdn()/,a[i].y=(db)rdn()/,a[i].z=-a[i].x-a[i].y;

  sort(a+,a+n+,cmp);

  for(int i=;i<m;i++) f[n+][i]=INF;

  for(int i=m,d=((n+)<<);i<=d;i++) f[n+][i]=;

  for(int i=n;i;i--)

    for(int j=,d=(i<<);j<=d;j++)

      {

    //    printf("i=%d j=%d\n",i,j);

    //    printf("f[i+1][j+1]=%.8lf f[i+1][j+2]=%.8lf\n",f[i+1][j+1],f[i+1][j+2]);

    if(f[i+][j+]==INF)

      {

        if(f[i+][j+]==INF)

          f[i][j]=INF;

        else f[i][j]=(a[i].y*f[i+][j+]+)/(-a[i].x-a[i].z);

      }

    else f[i][j]=(a[i].x*f[i+][j+]+a[i].y*f[i+][j+]+)/(-a[i].z);

    //    printf("f[%d][%d]=%.8lf\n",i,j,f[i][j]);

      }

  printf("%.8lf\n",f[][]);

  return ;

}