文章目錄

• 前言
• 題目描述
• • Input
  • Output
  • Sample Input
  • Sample Output
• 解析
• 代碼

前言

盡信書，則不如無書

題目描述

Input

僅有一行，該行給出依次兩個正整數N, M，分別表示寶石的個數和寶石在變化時可能變成的顏色種類數。

Output

應僅有一行，該行給出一個實數E?，表示圓環的“美觀程度”的期望值。

Sample Input

8 1

Sample Output

8.00000

解析

期望dp做的太少了，這題整了巨長時間，慢慢來吧qwq
設計dp不難，枚舉上一個同色塊即可，關鍵是對于環的處理
可以考慮給dp加一維：末尾是否與開頭相同
dp式也不難寫出
注意因為有m種顏色，枚舉顏色塊時所有合法的顏色都可以，所以要乘個m-1或者m-2之類的
關鍵是最后的統計答案！
大部分的題解統計答案都是：

for(int l=1;l<n;l++) ans+=l*l*dp[n-l][0]*mi[l-1];

我對dp[n-l][0] 這個玩意百思不得其解
怎么想怎么應該是dp[n-l+1][0]
最后發現是dp 邊界條件的原因
初始把dp[1][1]賦值成1然后從i=2開始推就好了

題解的那個dp定義感覺是把0當成起始元素，且強制令其與1顏色不同
這樣是可以自圓其說的
為什么要從0開始啊

總的來說，一定要自己多思考

代碼

#include<bits/stdc++.h> using namespace std; const int N=305; #define ll long long #define I register int ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m; double mi[N],dp[N][2]; int main(){n=read();m=read();mi[0]=1;for(int i=1;i<=n;i++) mi[i]=mi[i-1]/m;dp[1][1]=1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){dp[i][0]+=dp[j][0]*(i-j)*mi[i-j]*(m-2)+dp[j][1]*(i-j)*mi[i-j]*(m-1);dp[i][1]+=dp[j][0]*(i-j)*mi[i-j];}printf("i=%d dp0=%lf dp1=%lf\n",i,dp[i][0],dp[i][1]);}double ans=0;//printf("ans1=%lf\n",ans);for(int l=1;l<n;l++) ans+=l*l*dp[n-l+1][0]*mi[l-1];ans+=n*mi[n-1];printf("%.5lf",ans);return 0; } /* 1 17 6 0 3 4 8 12 16 */

總結

以上是生活随笔為你收集整理的YBTOJ：彩色圆环的全部內容，希望文章能夠幫你解決所遇到的問題。

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