傳送門

期望DP

設 f [ i ] 表示還有 i 個名字沒得到，集齊所有名字的期望購買次數

考慮一次購買的影響：

　　如果得到以前沒有的名字 f [ i-1 ] ?->? f [ i ]，如果得到有的名字 f [ i ] -> f [ i ]

那么可以得到 f [ i ] = f [ i-1 ] * (n-i)/n? + f [ i ] * i/n + 1（+1是因為購買了一次）

整理一下就是 f [ i ] = f [ i-1 ] + n/i

然后直接遞推就好了

然后要注意格式的輸出非常坑

　　　　　　　　　　233

分數要這樣輸出? ?2333----

　　　　　　　　　　2333

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; inline ll read() {ll x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f; } inline int count(ll x) {int res=0;while(x) res++,x/=10;return res; } ll gcd(ll a,ll b) { return b ? gcd(b,a%b) : a; }//gcd用來約分int n; ll a,b,c; int main() {n=read(); a=n; b=1;for(int i=2;i<=n;i++){a=a*i+b*n;b*=i;//通分int g=gcd(a,b);a/=g; b/=g;//約分 }c=a/b; a%=b;if(!a) { printf("%lld",c); return 0; }int lc=count(c);for(int i=1;i<=lc;i++) printf(" "); printf("%lld\n",a);int lb=count(b);if(c) printf("%lld",c); for(int i=1;i<=lb;i++) printf("-"); printf("\n");for(int i=1;i<=lc;i++) printf(" "); printf("%lld\n",b);return 0; }

?

?

轉載于:https://www.cnblogs.com/LLTYYC/p/9803337.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的P1291 [SHOI2002]百事世界杯之旅的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。