abc 314 e (期望dp

#include 
using namespace std;
using VI = vector<int>;
 
int n , m;
int c[110] , p[110];
VI g[110];
double dp[110];
 
int main(){
    cin>>n>>m;
    for(int i = 1;i <= n; i++){
        cin>>p[i]>>c[i];
        for(int j = 1; j <= c[i] ; j++){
            int x;
            cin>>x;
            g[i].push_back(x);
        }
    }
 
    for(int i = 1; i <= m ; i++){
        dp[i] = 1e9;
        for(int j = 1; j <= n ; j++){
            double d = 0 ;
            int cnt  = 0;
 
            for(int k = 0 ; k < c[j] ; k++){
                if(g[j][k] == 0) cnt++;
                else d += dp[max(0,i - g[j][k])]; 
            }
            //用第j个轮盘，达到i分所要花费的最小期望，如果有0代表是一次无效操作
            //
            // (c * p + d)/ c - cnt
            d += c[j] * p[j];
            d /= double(c[j] - cnt);
            dp[i] = min(dp[i] , d);
 
        }
        
    }
 
 
    printf("%.6lf" , dp[m]);
 
 
 
 
}

贴个别人的博客的解释

AtCoder Beginner Contest 314 - ~Lanly~ - 博客园 (cnblogs.com)

每次计算转第 j 个转盘所能达到 i 分的期望总和的代价，总和除以非 0 的次数 ，就是平均代价  

______________________________________________________________________

期望dp的状态应该从尾推头更加和理