洛谷2473 [SCOI2008]奖励关

Luogu

BZOJ

分析

好久以前写的题,竟然没写题解

$n$很小,考虑状压DP。

设$f[i][j]$表示$i$~$n$关,$1$~$i-1$宝物情况为$j$,$i$~$n$的最大得分期望。

因为是期望,所以考虑倒推。

状态转移方程容易得出:

如果$S$包含$k$,则$f[i][S]+=max(f[i+1][S],f[i+1][S|(1<<(k-1))]+P_k)$。

否则,$f[i][S]+=f[i+1][S]$。

每计算完一个状态后除以$n$就变成了期望值。

答案为$f[1][0]$。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
#define db long double
using namespace std;
inline int read()
{
    int X=0,w=1; char ch=getchar();
    while (ch<'0'||ch>'9') { if (ch=='-') w=-1; ch=getchar(); }
    while (ch>='0'&&ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
db f[110][1<<15]; //f[i][j]表示i~n关 1~i-1宝物情况为j i~n的最大得分期望
int p[16],lim,n,m;
bool e[16][16]; //e[i][j]表示有j才能捡i
bool yes[1<<15][16];
int main()
{
    n=read(); m=read(); lim=(1<<m)-1;
    for (re int i=1;i<=m;i++) {
        p[i]=read();
        int nxt=read();
        while (nxt) {
            e[i][nxt]=true;
            nxt=read();
        }
    }
    for (re int i=0;i<=lim;i++) {
        f[n+1][i]=0.0;
        for (re int j=1;j<=m;j++) {
            yes[i][j]=true;
            for (re int k=1;k<=m;k++) {
                if (e[j][k]&&(i&(1<<(k-1)))==0) {
                    yes[i][j]=false;
                    break;
                }
            }
        }
    }
    for (re int i=n;i>=1;i--)
        for (re int j=0;j<=lim;j++) {
            f[i][j]=0.0;
            for (re int k=1;k<=m;k++) {
                db ls=f[i+1][j];
                if (yes[j][k]) ls=max(ls,f[i+1][j|(1<<(k-1))]+p[k]);
                f[i][j]+=ls;
            }
            f[i][j]/=m;
        }
    printf("%.6Lf\n",f[1][0]);
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 57 PM

发表评论