【CF248E】Piglet's Birthday（动态规划）

题面

翻译：

给定\(n\)个货架，初始时每个上面有\(a[i]\)个蜜罐。

有\(q\)次操作，每次操作形如\(u,v,k\)，表示从货架\(u\)上任意选择\(k\)个蜜罐试吃（吃过的也还能吃），吃完后把这\(k\)个蜜罐放到\(v\)货架上去。

每次操作完之后回答所有蜜罐都被试吃过的货架数量的期望。

题解

发现没被吃过的数量对于每个货架而言都是单调不增的。

所以考虑没有被吃过的数量，设\(f[i][j]\)表示第\(i\)个货架有\(j\)个蜜罐没有被试吃的概率。

转移的话枚举当前试吃了几个没被吃过的蜜罐用组合数转移即可。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define ll long long#define MAX 100100inline int read(){ int x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x;}double f[MAX][111],ans;int n,q,a[MAX],b[MAX];double C(int n,int m){ if(n