ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[AtCoder Beginner Contest 263]E - Sugoroku 3(期望DP)

2022年8月7日 205点热度 0人点赞 0条评论

题目传送门:E - Sugoroku 3 (atcoder.jp)

题目大意 / Problem

有N个点(位置),其中从1到N - 1个点上各有一个骰子,在第i个点上可以投掷第i个骰子,假设在x位置上投到y,下一步就走到y上。保证下一个位置不会大于N。

问从位置1到位置N的步数期望,对998244353。

思路 / Thought

之前有写过期望的题《[LightOJ]Race to 1 Again(期望DP)》,但是和这道题还是有点区别的。

我们用dp[i]表示从i到N所需的期望步数。

显然应该从后往前进行dp,那么转移方程怎么写呢?

朴素的想法就是dp[i] = sum(dp[j]) / (a[i] + 1) + 1,j从i到i + a[i],意思是有1.0 / (a[i] + 1)的概率通过走1 + dp[j]步到终点N。

但是这里毕竟不能从dp[i]转移到dp[i]嘛,所以对dp[i]进行一个移项就好了。

最后的方程是dp[i] = (sum(dp[j]) + a[i] + 1) / a[i],j从i + 1到i + a[i]。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9, p = 998244353;
int a[maxn], N, dp[maxn], suffix[maxn];

int qmi(int a,int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)res = res * a % p;
		a = a * a % p, b >>= 1;
	}
	return res;
}

int inv(int x){return qmi(x, p - 2);}

void solve()
{
	cin >> N;
	for(int i = 1;i < N; ++ i)cin >> a[i];
	
	for(int i = N - 1;i >= 1; -- i)
	{
		dp[i] = (suffix[i + 1] - suffix[i + a[i] + 1] + p + a[i] + 1) * inv(a[i]) % p;
		suffix[i] = (suffix[i + 1] + dp[i]) % p;
	}

	cout << dp[1] << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int _ = 1;
	while(_ --)solve();
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder C++ DP 动态规划 期望dp
最后更新:2022年8月7日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号