P2473 [SCOI2008] 奖励关

Hehe_0 · 2021-08-07 15:01:18 · 题解

很经典的一道 状压Dp+期望 。 这篇题解比较基础些，dalao请绕路 。

我们观察数据范围： n \le 15 , 我们不难想到状态压缩 。 又由于我们取东西是有前后时间关系，也有选择的限制，所以我们将物品所选的状态压起来 。

用 dp [ i ] [ j ] 表示 我们在第 i 轮的所取过物品的状态为 j 所的最大值。（期望
接下来我们思考转移方程 ：
我们在考虑一个物品时有两个状态 :

1. 我们没有达到物品的要求 ， 我们没有办法在此轮拿它
2. 我们达到了要求，我们在 dp [ i ] [ j ] 要去找 dp [ i+1 ] [ j ] 和 dp [ i + 1 ] [ k * 2 - 1 ]

如果2情况不太会用代码实现的状压小白可以手玩一些数据 。 比如 我们现有状态为 1011001
.............而物品限制为 1001011

然后 & 出来的结果是 1001001
所以这个物品不可选 。

最后附上注释代码 。

#include<bits/stdc++.h>

using namespace std;
const int N=105;

int n,m;
//n个物品m轮 
//第i轮状态为j的最大收益
double dp[N][1<<15|1];
int a[N];//每个物品的值 
int limit[N];//第i个物品的限制状态 

int main()
{
    ios::sync_with_stdio(false);
    cin>>m>>n;

     for(int i=1;i<=n;i++)
     {
        cin>>a[i];
        int flag;
        while(cin>>flag&&flag)
            limit[i]|=(1<<flag-1);
//把当前物品的限制压到数组里     
     }

    for(int i=m;i>=1;i--)
    {//轮的次数，这里要倒着来 
        for(int j=0;j<=(1<<n);j++)
        {//状态 
            for(int k=1;k<=n;k++)   
            {//枚举所扔出来的物品 
                if((j&limit[k])>=limit[k])
                {// 达到了要求 
                    dp[i][j]+=max(dp[i+1][j],dp[i+1][j|(1<<k-1)]+a[k]);
                }
                else//没有达到要求 
                dp[i][j]+=dp[i+1][j];
            }   
            //由于我们需要求期望，并且有n个物品 
            dp[i][j]/=n;
        }
    }

    //控一下小数位， 
    printf("%.6lf",dp[1][0]);
    return 0;
}