感觉自己前几天没做什么题（晚上又忘了写博客...鸽了鸽了
2022-02-18
牛客竞赛动态规划专题 概率DP
恶意竞争
已知的条件是如果已有s个子组件和n类漏洞，那么不需要任何的一个步骤。即 ：
dp[s][n] = 0;
那么已知这个状态，我们可以做如下转移：
dp[i][j] = dp[i][j] * (i / s) * (j / n) + dp[i + 1][j] * ((s - i) / s) * (j / n) + dp[i][j + 1] * (i / s) * ((n - j) / n) + dp[i + 1][j + 1] * ((s - i) / s) * ((n - j) / n);
由于dp[i][j]在等式右边已经存在了，那么我们只需要将右边的dp[i][j]左移即可进行正常的转移
AC代码：
点击查看代码
#include <iostream>
using namespace std;
const int MAXN = 1003;
double dp[MAXN][MAXN];
int n,s;
double dfs(int x,int y)
{
if(x > n || y > s) return 0;
if(x == 0 && y != 0) return 0;
if(x != 0 && y == 0) return 0;
if(dp[x][y] != -1) return dp[x][y];
double ans = 0;
if(x == 0 && y == 0)
ans += (dfs(x + 1,y + 1) + 1);
else
{
int i = x,j = y;
ans = x * y;
ans += ((dfs(x + 1,y) + 1) * (n - i) * j);
ans += ((dfs(x,y + 1) + 1) * (s - j) * i);
ans += ((dfs(x + 1,y + 1) + 1) * (n - i) * (s - j));
ans /= (n * s - i * j);
}
return dp[x][y] = ans;
}
int main()
{
scanf("%d %d",&n,&s);
for(int i = 0;i <= n;++i)
for(int j = 0;j <= s;++j) dp[i][j] = -1;
dp[n][s] = 0;
printf("%.10f\n",dfs(0,0));
}
带富翁
筛子只有6点，那么当我们当前状态进行到了n的位置就不需要往后再进行移动了，这时的答案就是a[n];
我们可以设dp[i]为当前在第i个，最终到达第n个地方的期望得分；
枚举每次可能的筛子点数，进行相应的转移，具体如下：dp[i] += dp[i + k] (k∈[1,6])dp[i] /= cnt (cnt += (i + k <= n));dp[i] += a[i];
AC代码：
点击查看代码
#include <iostream>
using namespace std;
const int MAXN = 107;
int a[MAXN];
double dp[MAXN];
int n;
double dfs(int x)
{
if(x > n) return 0;
if(dp[x] != -1) return dp[x];
double ans = 0;
int cnt = 0;
for(int i = 1;i <= 6;++i)
{
ans += dfs(x + i);
cnt += (x + i <= n ? 1 : 0);
}
return dp[x] = ans / cnt + a[x];
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
for(int i = 0;i <= n;++i) dp[i] = -1;
dp[n] = a[n];
printf("%lf\n",dfs(1));
return 0;
}
筛子游戏
首先可以知道最后的结束状态就是x > n的时候可以不需要次数即：
i > n时：dp[i] = 0;
即dp[i]是从分数为i到分数 > n所需要的期望步数
那么观察一下之前的状态怎么转移到这个状态：
dp[i] = sum(dp[i + k] * p[k]) + dp[0] * p[0] + 1
k是挡墙筛子所摇出来的总点数，即k ∈ [3,k1 + k2 + k3];
但是右边有dp[0]这个状态，正是我们需要求的，显然破坏了dp的转移，因此需要找到另外一种方式转移：
我们将式子写成下面这样：
dp[i] = A[i] * dp[0] + B[i];
dp[i] = sum(A[i + k] * dp[0] * p[k] + B[i + k] * p[k]) + dp[0] * p[0] + 1;
dp[i] = (sum(A[i + k] * p[k]) + p[0]) * dp[0] + sum(B[i + k] * p[k]) + 1;
A[i] = (sum(A[i + k] * p[k]) + p[0]);
B[i] = sum(B[i + k] * p[k]) + 1;
dp[0] = dp[0] * A[0] + B[0];
只要求出来A[0]和B[0]就可直接求出dp[0]啦
而A、B的转移都是线性的~
AC代码：
点击查看代码
#include <iostream>
using namespace std;
const int MAXN = 607;
double A[MAXN],B[MAXN];
double p[MAXN];
int k1,k2,k3,a,b,c;
int n;
double dfs(int x)
{
if(x > n) return 0;
if(A[x] != -1) return A[x];
double ans = p[0];
for(int i = 3;i <= k1 + k2 + k3;++i)
ans += p[i] * dfs(i + x);
return A[x] = ans;
}
double dfs1(int x)
{
if(x > n) return 0;
if(B[x] != -1) return B[x];
double ans = 1;
for(int i = 3;i <= k1 + k2 + k3;++i)
ans += p[i] * dfs1(i + x);
return B[x] = ans;
}
int main()
{
scanf("%d %d %d %d %d %d %d",&n,&k1,&k2,&k3,&a,&b,&c);
for(int i = 0;i < MAXN;++i) A[i] = B[i] = -1;
double pp = 1.0 / k1 / k2 / k3;
for(int i = 1;i <= k1;++i)
for(int j = 1;j <= k2;++j)
for(int k = 1;k <= k3;++k)
{
if(i == a && j == b && k == c)
p[0] += pp;
else
p[i + j + k] += pp;
}
for(int i = n + 1;i <= n - 1 + k1 + k2 + k3;++i)
A[i] = B[i] = 0;
dfs(0);//A[i] = sum(A[i + x] * p[i]) + p[0];
dfs1(0);//B[i] = sum(B[i + x] * p[i]) + 1;
double ans = B[0] / (1 - A[0]);
printf("%.10lf\n",ans);
return 0;
}
食堂
由题目很容易设状态为dp[i][j]表示序列长度为i，当前位于j会排在队伍前k位的概率
j == 1时：
dp[i][1] = dp[i][i] * p2 + dp[i][1] * p1 + p4;
否则：
dp[i][j] = dp[i][j] * p1 + dp[i][j - 1] * p2 + dp[i - 1][j - 1] * p3 + p4 * (j <= k ? 1 : 0);
可以发现这里是都不能直接转移的，因此我们需要对式子进行进一步的简化
首先dp[i][1]和dp[i][j]是可以向左边合并的，然后
假设当前dp[i - 1]所有答案我们都已经知道了，那么：
p4和dp[i - 1][j - 1] * p3 + p4 * (j <= k)就是已知的，我们将它称为c[i];
那么dp[i][1] = dp[i][i] * p12 + c[1];
dp[i][j] = dp[i][j - 1] * p12 + c[j];
发现这其实构成了一个环，只需要求出其中一个答案，就可以线性得到其他答案。
很显然我们是可以对这个式子进行解方程的，只需要让两边都是相同的未知数即可
如:
dp[i][i] = dp[i][i - 1] * p12 + c[i];
dp[i][i] = (dp[i][i - 2] * p12 + c[i - 1]) * p12 + c[i];
...
dp[i][i] = (((dp[i][1] * p12 + c[2]) * p12 + c[3])...) * p12 + c[i];
再将dp[i][1]代为dp[i][i] * p12 + c[1]即可求解dp[i][i]~
AC代码：
点击查看代码
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
const int MAXN = 2007;
const double eps = 1e-10;
int n,m,k;
double p1,p2,p3,p4;
double dp[MAXN][MAXN];
double p12[MAXN],p14,p13;
/*
1 1 1 0.372818 0.318286 0.220035 0.0888615
*/
double dfs(int x,int y)
{
if(y > x) return 0;
else if(x == 0 || y == 0) return 0;
if(dp[x][y] != -1) return dp[x][y];
double ans = 0;
if(y == 1)
{
ans += p4;
double c = 0;
for(int i = 1;i <= x;++i)
{
if(i == 1)
c += (p14 * p12[x - i]);
else if(i <= k)
c += (dfs(x - 1,i - 1) * p13 + p14) * p12[x - i];
else
c += (dfs(x - 1,i - 1) * p13 * p12[x - i]);
}
dp[x][x] = c / (1 - p12[x]);
ans += dp[x][x] * p2;
return dp[x][y] = ans / (1 - p1);
}
ans += dfs(x,y - 1) * p2;
ans += dfs(x - 1,y - 1) * p3;
if(y <= k) ans += p4;
return dp[x][y] = ans / (1 - p1);
}
double c[MAXN];
int main()
{
while(~scanf("%d %d %d %lf %lf %lf %lf",&n,&m,&k,&p1,&p2,&p3,&p4))
{
if(fabs(p4) < eps)
{
puts("0.00000");
continue;
}
else if(fabs(p1 - 1) < eps)
{
puts("1.00000");
continue;
}
p14 = p4 / (1 - p1);
p13 = p3 / (1 - p1);
p12[0] = 1;
for(int i = 1;i < MAXN;++i)
p12[i] = p12[i - 1] * (p2 / (1 - p1));
dp[1][1] = p4 / (1 - p1 - p2);
// for(int i = 1;i <= n;++i)
// for(int j = 1;j <= m;++j) dp[i][j] = -1;
// /*
for(int i = 2;i <= n;++i)
{
double sum = 0;
for(int j = 1;j <= i;++j)
if(j == 1)
c[j] = p14;
else
c[j] = (dp[i - 1][j - 1] * p13 + (j <= k ? p14 : 0));
for(int j = 1;j <= i;++j) sum += c[j] * p12[i - j];
dp[i][i] = sum / (1 - p12[i]);
dp[i][1] = dp[i][i] * p12[1] + p14;
for(int j = 2;j < i;++j)
dp[i][j] = dp[i][j - 1] * p12[1] + c[j];
}
// */
// dfs(n,m);
printf("%.5f\n",dp[n][m]);
}
return 0;
}
数位DP练习
手机号码
dp[pos][pre2][pre1][p4][p8][pre];
表示前pos个，前一个数字为pre1,前两个数字为pre2,存在4?,存在8?,存在前导0?的符合条件的答案总数：
AC代码
点击查看代码
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 15;
typedef long long ll;
ll dp[MAXN][MAXN][MAXN][2][2][2];
int stk[MAXN];
/*
11100 11199
1 10
10000000000
99999999999
*/
ll dfs(int pos,int pre2,int pre1,bool p4,bool p8,bool ok,bool flag)
{
if(p4 && p8) return 0;
if(pos == 0) return ok;
if(flag && dp[pos][pre2][pre1][p4][p8][ok] != -1)
return dp[pos][pre2][pre1][p4][p8][ok];
int Max = flag ? 9 : stk[pos];
ll ans = 0;
for(int i = 0;i <= Max;++i)
ans += dfs(pos - 1,pre1,i,p4 || i == 4,p8 || i == 8,\
ok || (i == pre2 && i == pre1),flag || i != Max);
if(flag) return dp[pos][pre2][pre1][p4][p8][ok] = ans;
return ans;
}
ll cal(ll x){
int pos = 0;
if(x < 1e10) return 0;
while(x)
{
stk[++pos] = x % 10;
x /= 10;
}
ll ans = 0;
for(int i = 1;i <= stk[pos];++i)
ans += dfs(pos - 1,0,i,i == 4,i == 8,0,i != stk[pos]);
return ans;
}
int main()
{
memset(dp,-1,sizeof dp);
ll l,r;
scanf("%lld %lld",&l,&r);
printf("%lld\n",cal(r) - cal(l - 1));
return 0;
}
明七暗七
好朋友
COUNT数字计数
Balls
柯学送分
抽卡
上面几题较为基础...先偷个懒...
奖励关
一看数据范围，很显然会这样设置状态方程：
dp[i][s]表示前i个宝物，当前已拿取的宝物状态为s所能获得的最大期望分数
对于每个宝物的前置条件也用二进制串进行表示(ss[l],l∈[0,n - 1])
当ss[l] & s == ss[l]表示ss[l]是s的子集，可以拿第l件物品
现在考虑状态的转移：
如果我们从前往后进行转移，如果当前l物品拿的话，枚举之前状态j，转移即为：
dp[i][j | (1 << l)] = dp[i - 1][j] + p[l];
如果不拿的话：
dp[i][j] = dp[i - 1][j];
但是这样很显然，我们无法求得最大的那个策略...
因此我们从后往前进行转移，这样可以从后面那个较优的状态转移过来：
ss[l] & j == ss[l]
dp[i][j] += max(dp[i + 1][j],dp[i + 1][j | (1 << l)] + p[l]) * pp
否则
dp[i][j] += dp[i + 1][j] * pp;
pp是概率...
AC代码：
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 15;
double dp[105][1 << MAXN];
int p[MAXN],s[MAXN];
ll f[105][1 << MAXN];
pair<int,int> pre[105][1 << MAXN];
int main()
{
int k,n;
scanf("%d %d",&k,&n);
for(int i = 0;i < n;++i)
{
scanf("%d",&p[i]);
int c = 0;
scanf("%d",&c);
int ss = 0;
while(c != 0)
{
ss |= (1 << (c - 1));
scanf("%d",&c);
}
s[i] = ss;
}
/*
memset(f,0xcf,sizeof f);
f[0][0] = 0;
pre[0][0] = {-1,0};
for(int i = 1;i <= k;++i)
{
for(int j = 0;j < (1 << n);++j)
{
for(int l = 0;l < n;++l)
{
if((s[l] & j) != s[l]) continue;
if(f[i][j | (1 << l)] < f[i - 1][j] + p[i])
{
f[i][j | (1 << l)] = f[i - 1][j] + p[i];
pre[i][j | (1 << l)] = {l,j};
}
}
}
}
ll Max = -1e9,sta = 0;
for(int i = 0;i < (1 << n);++i)
{
if(Max < f[k][i])
{
Max = f[k][i];
sta = i;
}
}
int now = sta,m = n;
while(m != 0)
{
printf(">>%d\n",pre[m][now].first);
now = pre[m][now].second;
m -= 1;
}
*/
double pp = 1.0 / n;
for(int i = k;i >= 1;--i)
{
for(int j = 0;j < (1 << n);++j)
{
int cnt = 0;
for(int l = 0;l < n;++l)
if(j >> l & 1) cnt += 1;
if(cnt > i) continue;
for(int l = 0;l < n;++l)
{
if((s[l] & j) == s[l])
dp[i][j] += max((dp[i + 1][j | (1 << l)] + p[l]),dp[i + 1][j]) * pp;
else
dp[i][j] += dp[i + 1][j] * pp;
}
}
}
double ans = dp[1][0];
printf("%.6lf\n",ans);
return 0;
}