概率DP
$dp_i$表示连打$i$个字符的期望按键数
那么枚举保存的次数，均分一下连打的个数就好
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<string> 5 #include<cstring> 6 #include<cmath> 7 #define re(i,l,r) for(int i=(l);i<=(r);i++) 8 #define rre(i,r,l) for(int i=(r);i>=(l);i--) 9 using namespace std; 10 int n,x; 11 double p; 12 double dp[100010]; 13 int main() 14 { 15 int t,tt; 16 scanf("%d",&t);tt=t; 17 while(t--) 18 { 19 scanf("%d%lf%d",&n,&p,&x); 20 re(i,1,n)dp[i]=(dp[i-1]+1)/(1-p); 21 double ans=dp[n]+x; 22 re(i,2,n) 23 { 24 int shu=n/i; 25 if(n%i)ans=min(ans,dp[shu+1]*(n%i)+dp[shu]*(i-n%i)+i*x); 26 else ans=min(ans,dp[shu]*i+i*x); 27 } 28 printf("Case #%d: %.6f ",tt-t,ans); 29 } 30 return 0; 31 }