网站建设一般是用哪个软件,营销网站竞品分析报告,长沙市公司,网站做适配多少钱正题 题目大意 nnn个球排成一排颜色不同#xff0c;每次选择一个随机的[1..n][1..n][1..n]中的xxx#xff0c;然后删掉第xxx个或第n−x1n-x1n−x1个数#xff0c;求删kkk次之后删掉的白球最多#xff0c;求删掉数量的期望值 解题思路
考虑状态压缩dpdpdp#xff0c;定义第…正题 题目大意
nnn个球排成一排颜色不同每次选择一个随机的[1..n][1..n][1..n]中的xxx然后删掉第xxx个或第n−x1n-x1n−x1个数求删kkk次之后删掉的白球最多求删掉数量的期望值 解题思路
考虑状态压缩dpdpdp定义第一个111所在位数表示剩下的球数111表示该位置是白球000表示该位置是黑球。设fsf_sfs表示状态为sss时的最小期望值。
del(s,i)del(s,i)del(s,i)表示sss去掉第iii个球后的状态有状态转移方程fs∑i1lmax{fdel(s,i)one(s,i),fdel(s,n−i1)one(s,n−i1)}lf_s\frac{\sum_{i1}^lmax\{f_{del(s,i)}one(s,i),f_{del(s,n-i1)}one(s,n-i1)\}}{l}fsl∑i1lmax{fdel(s,i)one(s,i),fdel(s,n−i1)one(s,n−i1)}
这样的时间复杂度为O(2nn)O(2^nn)O(2nn)
但是有许多状态是没有使用的我们对于小的sss可以用一个桶存对于大的sss我们可以用mapmapmap来存即可 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includemap
#define XJQ using
#define AK namespace
#define IOI std
XJQ AK IOI;
const int N35,Lim124;
int n,k;
double a[Lim];
mapint,double m;
char str[N];
bool live(int x,int l){int zx|(1l);if(zLim)return (a[z]!-1);return m.count(z);
}
double get(int x,int l){int zx|(1l);if(zLim)return a[z];return m[z];
}
void change(int x,int l,double val){int zx|(1l);if(zLim) a[z]val;else m[z]val;return;
}
int del(int x,int w)
{return ((xw1)w)x%(1w);}
double dfs(int s,int l){if(ln-k)return 0;if(live(s,l))return get(s,l);double ans0;for(int i0;il;i) ans(max(dfs(del(s,i),l-1)((si)1),dfs(del(s,l-i-1),l-1)((s(l-i-1))1)))/l;change(s,l,ans);return ans;
}
int main()
{scanf(%d%d,n,k);scanf(%s,str);int s0;for(int i0;iLim;i)a[i]-1;for(int i0;in;i)s|((str[i]W)i);printf(%.6lf,dfs(s,n));
}
