概率DP

$dp_i$表示连打$i$个字符的期望按键数

那么枚举保存的次数，均分一下连打的个数就好

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            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\n",tt-t,ans);29 }30 return 0;31 }