题意简述
有种能量圈,第
种能量是
。开始你没有能量圈。对于每一天,你有
的概率失去一个能量最小的能量圈,有
的概率可以等概率得到一个能量不大于你现有最小能量圈的能量圈。如果你现在没有能量圈,则不存在概率失去能量圈。
求第一次能量总和超过的期望天数。
算法讨论
考虑如果我们知道如何表示一个状态,则不妨设其为。
设为
达到终态的期望步数。有
特殊地,对于初始状态有
高斯消元显然可以解决,但是复杂度过高。我们考虑深入挖掘问题的性质。
仔细观察式子,我们发现,对于一个状态,至多有一个状态
是它的前驱,且存在状态
没有前驱。这是一棵树!一个状态的期望仅和它的儿子和父亲有关。
于是我们如果从叶子节点推起,就可以将一个结点的期望化简成的形式。一直推到根结点就得到了答案。
所有只有如何表示状态的问题啦。
考虑到naive的状态表示,就是把每一次得到的能量圈记录下来。我们发现这样其实是可行的,因为有效的状态中能量圈的能量之和必定不超过,而
的正整数拆分数约为
,是可承受的。
时间复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ // (1 - a) E[v] = b + p E[lst[v]] // E[v] = (1 - p) (1 / |nxt[v]| \sum_{nxt[v]}) + p E[lst[v]] + 1 // E[init] = 1 / nxt[v] \sum_{nxt[v]} + 1 struct node { double x,y; node(double a=0,double b=0):x(a),y(b) {} }; node operator + (node a,node b) { return node(a.x+b.x,a.y+b.y); } node operator * (node a,double w) { return node(a.x*w,a.y*w); } int a[55],b[55]; double p; int T,n; inline int chk(int i,int j) {return i>j;} node dfs(int x,int s) { int cnt=0; if(s>T) return node(0,0); node res=node(0,0); REP(i,1,n) if(a[i]<=b[x]) { b[x+1]=a[i];++cnt; res=res+dfs(x+1,s+a[i]); } res=res*(1.0/cnt); if(x) res=res*(1-p);res=res+node(0,1); node tmp=node(p,res.y)*(1.0/(1-res.x)); return node(p,res.y)*(1/(1-res.x)); } void solve() { REP(i,1,n) read(a[i]); sort(a+1,a+n+1,chk);b[0]=(int)(1e9); printf("%.3lf\n",dfs(0,0).y); } int main() { while(scanf("%lf%d%d",&p,&T,&n)==3) solve(); return 0; } |