P1291 [SHOI2002] 百事世界杯之旅 概率与期望 dp
P1291 [SHOI2002] 百事世界杯之旅
如果现在已经有了 \(x\) 个名字，那么使名字达到 \(x+1\) 平均需要 \(\frac{n}{n-x}\) 瓶，所以：
\[ans=n\times\sum_{i=1}^{n}(\frac{1}{i})
\]
如果硬要写成 dp 的话，就是：
\[dp_i=dp_{i-1}+\frac n i
\]
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int getnum(int x) {
int ret=0;
while(x) {
x/=10;
ret++;
}
return ret;
}
struct frac {
int fz,fm;
void print() {
int l=fz/fm,r=fz%fm,dl=0,dr=0,dm=0;
if(l)dl=getnum(l);
if(!r) {
cout<<l<<endl;
return;
}
dr=getnum(r);
dm=getnum(fm);
for(int i=1; i<=dl; i++) {
cout<<' ';
}
cout<<r<<endl;
cout<<l;
for(int i=1; i<=dm; i++) {
cout<<'-';
}
cout<<endl;
for(int i=1; i<=dl; i++) {
cout<<' ';
}
cout<<fm<<endl;
}
void yuefen() {
int g=__gcd(fz,fm);
fz/=g;
fm/=g;
return;
}
friend frac operator +(frac a,frac b) {
frac ret;
ret.fm=a.fm*b.fm;
ret.fz=a.fz*b.fm+b.fz*a.fm;
ret.yuefen();
return ret;
}
} dp[40];
signed main() {
cin>>n;
dp[0]= {0,1};
for(int i=1; i<=n; i++) {
dp[i]=dp[i-1]+(frac) {
n,i
};
}
dp[n].print();
return 0;
}