G - Damaged Bicycle 状压+最短路
最短路处理出1号节点和带车子的点到n的距离dist[x][n],G可以从节点1直接走到n，也可以从节点1走到带车子的节点再骑到n，如果车子坏了可以走到n，也可以走到下一个车子节点再进行之前的步骤，所以可以记忆化搜索一下，dp[sta][x]，sta表示走了几个关键点，是一个压缩的二进制，x是当前的关键点，转移就是
dp[sta][x]=min(dp[sta][x],1.0*(1-p[x])*dist[x][n]/r+p[x]*(1.0*dist[x][a[i]]/t+dfs(sta|(1<
该点的车子没坏的期望加上坏了走到下一个关键点的期望
【超好懂的比赛题解】2021CCPC哈尔滨站 个人题解_RWLinno的博客-CSDN博客
#include
#define int long long
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=1e6+5;
const int inf=1e18;
double t,r;
int n,m,head[N],cnt,k,a[22];
struct Edge
{int next,to;int w;
}e[N];
void addedge(int from,int to,int w)
{e[++cnt].next=head[from];e[cnt].to=to;e[cnt].w=w;head[from]=cnt;
}
int vis[N],dist[22][N];
double dp[N][22],p[22];
struct node
{int id,dis;bool operator<(const node &a)const{return a.disq;q.push(node{s,0});while(!q.empty()){node u=q.top();q.pop();int now=u.id;double dis=u.dis;if(vis[now]) continue;vis[now]=1;for(int i=head[now];i;i=e[i].next){int j=e[i].to;if(dist[num][now]+e[i].w>i-1)&1) continue;res=min(res,1.0*(1-p[x])*dist[x][n]/r+p[x]*(1.0*dist[x][a[i]]/t+dfs(sta|(1<>t>>r>>n>>m;for(int i=1;i<=m;i++){int u,v;double w;cin>>u>>v>>w;addedge(u,v,w);addedge(v,u,w);}cin>>k;a[0]=1;p[0]=1;for(int i=1;i<=k;i++){cin>>a[i]>>p[i];p[i]/=100.0;}for(int i=0;i<=k;i++) dij(a[i],i);double ans=dfs(0,0);if(dist[0][n]>=inf) cout<<"-1\n";else cout< D-七圣召唤_概率dp
第一个设dp[i]为抽到i种卡片需要的期望次数，显然dp[1]=1,然后
意思就是有
第二个答案f[i],可以理解成f[i]=(k-f[i-1])/k+f[i-1],在i-1次的基础上加上这一次成功的概率，应该说是期望，理解是价值为1，所以就直接加上了
2022 年辽宁省大学生程序设计竞赛 个人题解_RWLinno的博客-CSDN博客_辽宁省程序设计大赛
#include
#define int long long
#define endl '\n'
#define pause system("pause")
using namespace std;
const int N=1e6+5;
const int inf=1e18;
int n,k;
double qpow(double a,int b)
{double res=1.0;while(b){if(b&1) res=res*a;a=a*a;b>>=1;}return res;
}
double dp[N],f[N];
signed main()
{//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;dp[0]=0;dp[1]=1;for(int i=2;i<=k;i++){dp[i]=(1.0*(k-i+1)*dp[i-1]/k+1.0)*k/(k-i+1);//cout<
