BZOJ 3029: 守卫者的挑战

今天整套题当模拟赛做的

一开始想是概率 dp

然后看见容量这么大数组开不下果断搜索。。

然后30分。。。

最后正解概率 dp 。。。

后来一想的确沙茶了，背包容量大于200果断剩余部分是用不到的。。

然后就可以开下数组惹

然后就过了

我习惯用记忆化搜索的方法写。。

虽然常数似乎有点大。。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define g getchar()
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
inline ll read(){
    ll x=,f=;char ch=g;
    for(;ch<'0'||ch>'9';ch=g)if(ch=='-')f=-;
    for(;ch>='0'&&ch<='9';ch=g)x=x*+ch-'0';
    return x*f;
}
inline void out(ll x){
    int a[],t=;
    if(x<)putchar('-'),x=-x;
    for(;x;x/=)a[++t]=x%;
    for(int i=t;i;--i)putchar('0'+a[i]);
    if(t==)putchar('0');
    putchar('\n');
}
struct re{int v;double p;}a[];
int n,L,sum[],k,cnt;
double f[][][];
double dfs(int now,int win,int v){
    if(now>n){
        if(win>=L&&v>=)return f[now][win][v]=;
        else return ;
    }
    if(v<)return f[now][win][v]=;
    if(L-win>n-now+)return f[now][win][v]=;
    if(f[now][win][v]>-)return f[now][win][v];
//  if(win>=L&&v>=sum[now])return f[now][win][v]=1;
    f[now][win][v]=;
    f[now][win][v]+=dfs(now+,win+,v+a[now].v>?:v+a[now].v)*a[now].p;
    f[now][win][v]+=dfs(now+,win,v)*(-a[now].p);
    return f[now][win][v];
}
inline bool cmp(re x,re y){return x.v==y.v?x.p>y.p:x.v>y.v;}
int main(){
//  freopen("guard10.in","r",stdin);
//  freopen("guard.out","w",stdout);
    n=read();L=read();k=read();k=k>?:k;
    for(int i=;i<=n;++i){scanf("%lf",&a[i].p);a[i].p/=;}
    for(int i=;i<=n;++i){a[i].v=read();if(a[i].v==-)++cnt;}
    sort(a+,a++n,cmp);
    for(int i=;i<=;++i)for(int j=;j<=;++j)for(int k=;k<=;++k)f[i][j][k]=-;
    for(int i=n;i;--i)if(a[i].v==-)sum[i]=sum[i+]-a[i].v;else sum[i]=sum[i+];
    dfs(,,k);
    printf("%.6lf\n",f[][][k]);
    return ;
}