外包做网站的要求怎么写,安卓开发软件工具,微信开发者工具怎么用,国土局网站建设经验problem
luogu
现有N(1≤N≤300)N(1 ≤ N ≤ 300)N(1≤N≤300) 个盘子#xff0c;编号为1,2,3,…,N1,2,3,…,N1,2,3,…,N。
第 iii个盘中放有 ai(1≤ai≤3)a_i(1≤a_i ≤3)ai(1≤ai≤3)个寿司。
接下来每次执行以下操作#xff0c;直至吃完所有的寿司。
从第 1,2,3,…problem
luogu
现有N(1≤N≤300)N(1 ≤ N ≤ 300)N(1≤N≤300) 个盘子编号为1,2,3,…,N1,2,3,…,N1,2,3,…,N。
第 iii个盘中放有 ai(1≤ai≤3)a_i(1≤a_i ≤3)ai(1≤ai≤3)个寿司。
接下来每次执行以下操作直至吃完所有的寿司。
从第 1,2,3,…,N1,2,3,…,N1,2,3,…,N 个盘子中任选一个盘子吃掉其中的一个寿司。若没有寿司则不吃。
若将所有寿司吃完请问此时操作次数的数学期望是多少
solution
最直接地设 f(a1,a2,a3,...,an):f(a_1,a_2,a_3,...,a_n):f(a1,a2,a3,...,an): 第 iii 盘还剩 aia_iai 个寿司的期望次数。
那么枚举随机到的盘子有方程f(a1,a2,...,an)1∑i1n1nf(a1,a2,...,max(ai−1,0),...,an)f(a_1,a_2,...,a_n)1\sum_{i1}^n\frac{1}{n}f(a_1,a_2,...,\max(a_i-1,0),...,a_n)f(a1,a2,...,an)1∑i1nn1f(a1,a2,...,max(ai−1,0),...,an)。
显然这个等式不能构成转移方程因为存在原地打转第 iii 盘寿司为空时就变成了自身转移到自身状态不变的情况。
由于随机均匀分布盘子的位置是不重要的事实上我们真正关注的只有盘子中剩余寿司的数量。
而 aia_iai 寿司数量又只有四种取值 0/1/2/30/1/2/30/1/2/3。
不妨重新设 f(o,i,j,k):f(o,i,j,k):f(o,i,j,k): 当前还剩下 o/i/j/ko/i/j/ko/i/j/k 个盘子中有 0/1/2/30/1/2/30/1/2/3 个寿司。
则有转移 f(o,i,j,k)1onf(o,i,j,k)inf(o1,i−1,j,k)jnf(o,i1,j−1,k)knf(o,i,j1,k−1)f(o,i,j,k)1\frac{o}{n}f(o,i,j,k)\frac{i}{n}f(o1,i-1,j,k)\frac{j}{n}f(o,i1,j-1,k)\frac{k}{n}f(o,i,j1,k-1) f(o,i,j,k)1nof(o,i,j,k)nif(o1,i−1,j,k)njf(o,i1,j−1,k)nkf(o,i,j1,k−1)
n−onf(o,i,j,k)1inf(o1,i−1,j,k)jnf(o,i1,j−1,k)knf(o,i,j1,k−1)\frac{n-o}{n}f(o,i,j,k)1\frac{i}{n}f(o1,i-1,j,k)\frac{j}{n}f(o,i1,j-1,k)\frac{k}{n}f(o,i,j1,k-1) nn−of(o,i,j,k)1nif(o1,i−1,j,k)njf(o,i1,j−1,k)nkf(o,i,j1,k−1)
f(o,i,j,k)nijkiijkf(o1,i−1,j,k)jijkf(o,i1,j−1,k)kijkf(o,i,j1,k−1)f(o,i,j,k)\frac{n}{ijk}\frac{i}{ijk}f(o1,i-1,j,k)\frac{j}{ijk}f(o,i1,j-1,k)\frac{k}{ijk}f(o,i,j1,k-1) f(o,i,j,k)ijknijkif(o1,i−1,j,k)ijkjf(o,i1,j−1,k)ijkkf(o,i,j1,k−1)
这样就不存在状态相同的死循环转移了。
但是现在是 O(n4)O(n^4)O(n4) 的需要进一步优化。
不难发现盘子数量是固定不变的即 oijknoijknoijkn所以当我们知道了其中任意三个数就能推出剩下一个数。
设 f(i,j,k):f(i,j,k):f(i,j,k): 当前还剩下 i/j/ki/j/ki/j/k 个盘子中有 1/2/31/2/31/2/3 个寿司。 f(i,j,k)nijkiijkf(i−1,j,k)jijkf(i1,j−1,k)kijkf(i,j1,k−1)f(i,j,k)\frac{n}{ijk}\frac{i}{ijk}f(i-1,j,k)\frac{j}{ijk}f(i1,j-1,k)\frac{k}{ijk}f(i,j1,k-1) f(i,j,k)ijknijkif(i−1,j,k)ijkjf(i1,j−1,k)ijkkf(i,j1,k−1) 最后还要注意循环枚举的细节
kkk 只用了 k−1k-1k−1当在 (i,j)(i,j)(i,j) 时会问到 j1j1j1所以 kkk 要在 jjj 循环的外层。同理 jjj 会用到同 kkk 下的 j1j1j1但此时是 i−1i-1i−1所以 jjj 循环要在 iii 的外层。综上我们确定唯一的循环顺序是 k,j,ik,j,ik,j,i。
时间复杂度 O(n3)O(n^3)O(n3)。
code
#include bits/stdc.h
using namespace std;
#define maxn 305
double f[maxn][maxn][maxn];
int a[5];
int n;
int main() {scanf( %d, n );for( int i 1, x;i n;i ) scanf( %d, x ), a[x] ;for( int k 0;k n;k )for( int j 0;j n;j )for( int i 0;i n;i )if( i or j or k ) {if( i ) f[i][j][k] f[i - 1][j][k] * i / (i j k);if( j ) f[i][j][k] f[i 1][j - 1][k] * j / (i j k);if( k ) f[i][j][k] f[i][j 1][k - 1] * k / (i j k);f[i][j][k] n * 1.0 / (i j k);} printf( %.10f\n, f[a[1]][a[2]][a[3]] );return 0;
}
