bzoj 3029 守卫者的挑战——概率期望dp+状态数思考

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3029

先随便写了个dfs，记录“前 i 次、成功 j 次、容量-残片=k”的概率。因为是否可行只和“成功次数”还有“容量-残片个数”有关，和容量、残片具体数量无关。准备记忆化，但发现状态存不下。

#include<iostream>

#include<cstdio>

#include<cstring>

#define db double

using namespace std;

const int N=,M=;

int n,l,K,a[N];

db p[N],ans;

void dfs(int i,int j,int c,double w)//至少有c个

{

    if(c>n)c=n;

    if(i>n)

    {

        if(j>=l&&c>=)ans+=w;return;

    }

    if(j+(n-i+)<l)return;

    if(a[i]>=)

    {

        dfs(i+,j+,c+a[i],w*p[i]);

        dfs(i+,j,c,w*(-p[i]));

    }

    else

    {

        dfs(i+,j+,c-,w*p[i]);

        dfs(i+,j,c,w*(-p[i]));

    }

}

int main()

{

    scanf("%d%d%d",&n,&l,&K);int x;

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

    {

        scanf("%d",&x);p[i]=(db)x/;

    }

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    dfs(,,K,);

    printf("%.6lf\n",ans);

    return ;

}

然后想到了 bzoj4247 挂饰的思路。就是发现“容量-残片数量”大于n的话多出来的部分没什么用，可以把大于n记成等于n。这样第三维就只有2*n啦！然后就可以刷表了。

#include<iostream>

#include<cstdio>

#include<cstring>

#define db double

using namespace std;

const int N=,M=;

int n,l,K,a[N];

db p[N],ans,dp[][N][N<<];

int main()

{

    scanf("%d%d%d",&n,&l,&K);int x;

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

    {

        scanf("%d",&x);p[i]=(db)x/;

    }

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    dp[][][min(n,K)+N]=;

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

    {

        int d=(i&);

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

            for(int k=-n;k<=n;k++)dp[!d][j][k+N]=;

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

            for(int k=-n;k<=n;k++)

            {

                if(a[i+]>=)

                {

                    dp[!d][j+][min(n,k+a[i+])+N]+=dp[d][j][k+N]*p[i+];//+=

                    dp[!d][j][k+N]+=dp[d][j][k+N]*(-p[i+]);

                }

                else

                {

                    dp[!d][j+][k-+N]+=dp[d][j][k+N]*p[i+];

                    dp[!d][j][k+N]+=dp[d][j][k+N]*(-p[i+]);

                }

            }

    }

    int d=(n&);

    for(int j=l;j<=n;j++)

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

            ans+=dp[d][j][k+N];

    printf("%.6lf\n",ans);

    return ;

}

巴特西

bzoj 3029 守卫者的挑战——概率期望dp+状态数思考

最新文章

热门文章