本文迁移自洛谷原文。
题目大意：
一款游戏中有 种装备，你一开始每种装备各有 个，且每种装备的初始等级均为 。游戏中可以靠打怪来获取新装备，总共有 只怪兽，每打赢 只怪兽后会随机获得一种装备 。假设原有的 装备的等级为 ，那么新获得的装备的等级为 ，且你会将新获得的装备和原来的装备中等级较高的装备留下，等级较低的装备卖出，卖出可获得的金币为该装备的等级。 问打完这 只怪兽后，获得的金币的期望。
题解：
期望 dp
观察到这 种装备都是“一样”的，所以我们可以随便选择一种装备来考虑它在打这 个怪兽时是如何变化的，然后对答案乘上 就可以了。
令 表示考虑到 还剩 个怪兽没打，且此时装备的等级为 时的期望答案。
为什么是 还剩 个怪兽，而不是 打了 个怪兽呢？因为如果我们如果设计是打了 个怪兽的话，每次往后转移的时候还要考虑到这种情况出现的概率，不好处理。而如果从后往前转移的话，就避免了复杂的计算。
这个trick在期望题中很常用
考虑转移。
卖掉了原有的等级为 的装备，可能性为 ，收益为
那就相当于拿到了又卖了
可能性为 ，收益为
可能性为 ，对其它装备有影响，而对这个装备的收益为
但发现这个方程的转移是 的，无法通过。
你想了想，发现这题要求输出的是小数，就打算在这上面动心思。
考虑每一次升级的概率。
从 级升到 的期望次数为 ，所以从 级升到 级的期望次数为
发现到了后面就很大可能不会再升级了。
所以，我们可以假定一个最大等级 ，当达到最大等级后就不再升级，这样也是在误差范围内的。
Code:
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
| using namespace std;
int n;
#define ld long double
ld dp[2][1005],k;
inline void solve(){
cin>>n>>k;
int cur=0,pre=1;
for(int i=1;i<=n;++i){
for(int j=1;j<=1000;++j){
dp[cur][j]=0;
dp[cur][j]+=(dp[pre][j+1]+j)/(j+1)/k;
dp[cur][j]+=(dp[pre][j]+(j+1.0)/2.0)*1.0*j/k/(1.0*(j+1));
dp[cur][j]+=(dp[pre][j])*(k-1)/k;
}
swap(cur,pre);
}
cout<<fixed<<setprecision(9)<<dp[pre][1]*k<<'\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
for(;T--;)solve();
return 0;
}
|