zoj 3640 Help Me Escape 期望DP 简单题 适合记忆化搜索

因为终点不确定，而且范围灰常大，数组根本存不下所有状态，就算存下了，初始化也要浪费不少时间。

所以必须记忆化搜索。

虽然AC了，下面的代码有一定的问题：问题在于对于浮点数，不能这么判断 if(dp[x]!=-1)，改成if(dp[x]>-0.5)

即可，但是ZOJ崩了，交不了了。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<climits>
#include<queue>
#include<vector>
#include<map>
#include<sstream>
#include<set>
#include<stack>
#include<cctype>
#include<utility>
#pragma comment(linker, "/STACK:102400000,102400000")
#define PI (4.0*atan(1.0))
#define eps 1e-10
#define sqr(x) ((x)*(x))
#define FOR0(i,n)  for(int i=0 ;i<(n) ;i++)
#define FOR1(i,n)  for(int i=1 ;i<=(n) ;i++)
#define FORD(i,n)  for(int i=(n) ;i>=0 ;i--)
#define  lson   ind<<1,le,mid
#define rson    ind<<1|1,mid+1,ri
#define MID   int mid=(le+ri)>>1
#define zero(x)((x>0? x:-x)<1e-15)
#define mk    make_pair
#define _f     first
#define _s     second
using namespace std;
//const int INF=    ;
typedef long long ll;
//const ll inf =1000000000000000;//1e15;
//ifstream fin("input.txt");
//ofstream fout("output.txt");
//fin.close();
//fout.close();
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
const int INF =0x3f3f3f3f;
const int maxn= 10000   ;
int maxi=0;
int c[maxn+10];
//const int maxm=    ;


int n,f;
double E,dp[maxn+10];
int time(double x)
{
    return (1+sqrt(5.0) )/2*x*x;
}

double DP(int x)
{
    if(x>maxi)  return E;
    if(dp[x]!=-1)   return dp[x];
    dp[x]=0;
    for(int i=1;i<=n;i++)
    {
        if(x>c[i])  dp[x]+=1.0/n*time(c[i]);
        else dp[x]+=1.0/n*(1+DP(x+c[i])  );
    }
    return dp[x];
}

void pre()
{
    E=0;
    for(int i=1;i<=n;i++)
    {
        E+=time(c[i]);
    }
    E/=n;
}

int main()
{
    while(~scanf("%d%d",&n,&f) )
    {
        maxi=0;
        FOR1(i,n)  {scanf("%d",&c[i]);maxi=max(maxi,c[i]); }
        pre();
        for(int i=f;i<=maxi;i++)   dp[i]=-1;
        printf("%.3f\n",DP(f) );

    }


    return 0;
}