• It provides full-frame, sub-sampled, windowed or arbitrarily scaled 8-bit/10-bit images in various formats via the control of the Serial Camera Control Bus (SCCB) interface or MIPI interface. The OV...
• 题意：一个人在迷宫里面，这个人有f的攻击力。他一共有n条通道可供随机选择，每次等概率随机选择一条。对每条通道i有参数c[i]。选择通道k后，若f > c[k]，则花费时间t[k]逃出迷宫，否则花费一天，攻击力f...设d[i...
题意：一个人在迷宫里面，这个人有f的攻击力。他一共有n条通道可供随机选择，每次等概率随机选择一条。对每条通道i有参数c[i]。选择通道k后，若f > c[k]，则花费时间t[k]逃出迷宫，否则花费一天，攻击力f增加c[k]，且一天之后继续选择通道。求逃出去所花费的天数的期望。其中t[k] = (int)((1+√5) * c[k]*c[k] / 2)。
解法：概率DP加记忆化写法。设d[i]表示当攻击力为i逃出去所花费的天数的期望，遍历每个通道j，若i > c[j]则d[i] += t[j] / n，否则d[i] += (1 + d[i+c[j]]) / n。
tag:概率DP，记忆化  1 /*
2  * Author:  Plumrain
3  * Created Time:  2013-11-16 19:38
4  * File Name: DP-ZOJ-3640.cpp
5  */
6 #include <iostream>
7 #include <cstdio>
8 #include <cmath>
9 #include <algorithm>
10
11 using namespace std;
12
13 int n, f;
14 int c;
15 double x;
16
17 double DP(int f)
18 {
19     double ret = 0.0;
20     for (int i = 1; i <= n; ++ i){
21         if (f > c[i]) ret += (int)(x * c[i] * c[i]);
22         else ret += 1 + DP(f+c[i]);
23     }
24     ret /= (double)n;
25     return ret;
26 }
27
28 int main()
29 {
30     x = (1 + sqrt(5)) / (double)2;
31     while (scanf ("%d%d", &n, &f) != EOF && n){
32         for (int i = 1; i <= n; ++ i)
33             scanf ("%d", &c[i]);
34         printf ("%.3f\n", DP(f));
35     }
36     return 0;
37 }

View Code

转载于:https://www.cnblogs.com/plumrain/p/ZOJ_3640.html
展开全文 • 题目大意: 人需要逃出地洞，每个地洞有自己的守卫者。守护者的战力为c[i]。 每天人会被随机的分配到一个地洞的出口前。 当人的战力值f&...c[i]时花费天即可逃出。...否则，战力值加上c[i]，天数... c[j] ， d[i] +=...
题目大意:

人需要逃出地洞，每个地洞有自己的守卫者。守护者的战力为c[i]。

每天人会被随机的分配到一个地洞的出口前。

当人的战力值f>c[i]时花费 天即可逃出。

否则，战力值加上c[i]，天数加一，第二天随机出现在一个地洞口。

问逃出去的天数的期望值。

题目分析：

分类讨论

d[i]是武力值为i的时候逃出地洞需要天数的期望值。

1.i> c[j] ， d[i] += floor(1+sqrt(5.0))/2 *c[i]^2/n

2.i <= c[j] ，d[i] +=(d(i+c[i])+1)/n

答案就是d[f]

#include <bits/stdc++.h>
using namespace std;
#define N 20005
double d[N];
double c[N];
double p = 0.5+sqrt(5.0)/2;
int n,f;
double dp(int tf){
//if(tf>N)tf = N-1;
if(d[tf]>0)return d[tf];
for(int i=0;i<n;i++){
if(tf>c[i]){
d[tf]+=floor(p*c[i]*c[i])/n;
}else {
d[tf]+=(dp(tf+c[i])+1)/n;
}
}
return d[tf];
}
int main(){
//std::ios::sync_with_stdio(false);
while(cin>>n>>f){
for(int i=0;i<n;i++){
cin>>c[i];
}
memset(d,0,sizeof(d));
printf("%.3f\n",dp(f));
}
}



展开全文 • 设$f[i][j]$表示$hp$为$i$，在$j$点的概率，$d[i]$表示$i$的度数，$w[i]$表示经过$i$点要扣掉的血量。 对于$j$到$k$这条边，$f[i-w[k]][k]+=\frac{f[i][j]}{d[j]}$。 若$w[k]>0$，则直接将贡献加给$f[i-w[k]][k... 设$f[i][j]$表示$hp$为$i$，在$j$点的概率，$d[i]$表示$i$的度数，$w[i]$表示经过$i$点要扣掉的血量。 对于$j$到$k$这条边，$f[i-w[k]][k]+=\frac{f[i][j]}{d[j]}$。 若$w[k]>0$，则直接将贡献加给$f[i-w[k]][k]$，否则加入转移矩阵$G$。 对于当前层，有$G\times f'[i]=f[i]$，即$f'[i]=G^{-1}\times f[i]$，对$G$求出逆矩阵即可。 时间复杂度$O(n^3+n^2hp)\$。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=152,M=10010;
int n,m,hp,i,j,k,w[N],g[N],v[M],nxt[M],ed;
double t,a[N][N],b[N][N],d[N],f[M][N],c[N],ans;
void add(int x,int y){d[x]+=1;v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
int main(){
scanf("%d%d%d",&n,&m,&hp);
for(i=1;i<=n;i++)scanf("%d",&w[i]);
while(m--){
scanf("%d%d",&i,&j),add(i,j);
if(i!=j)add(j,i);
}
for(i=1;i<=n;i++)d[i]=1.0/d[i];
for(i=1;i<=n;i++){
if(i<n)for(j=g[i];j;j=nxt[j])if(!w[v[j]])a[v[j]][i]-=d[i];
a[i][i]+=1,b[i][i]=1;
}
for(i=1;i<=n;i++){
for(k=i,j=i+1;j<=n;j++)if(fabs(a[j][i])>fabs(a[k][i]))k=j;
if(k!=i)for(j=1;j<=n;j++)swap(a[i][j],a[k][j]),swap(b[i][j],b[k][j]);
for(j=i+1;j<=n;j++)for(t=a[j][i]/a[i][i],k=1;k<=n;k++)a[j][k]-=a[i][k]*t,b[j][k]-=b[i][k]*t;
}
for(i=n;i;i--){
for(j=n;j>i;j--)for(t=a[i][j],k=1;k<=n;k++)a[i][k]-=a[j][k]*t,b[i][k]-=b[j][k]*t;
for(t=a[i][i],j=1;j<=n;j++)a[i][j]/=t,b[i][j]/=t;
}
f[hp]=1;
for(i=hp;i;i--){
for(j=1;j<=n;j++)for(c[j]=0,k=1;k<=n;k++)c[j]+=b[j][k]*f[i][k];
ans+=c[n],c[n]=0;
for(j=1;j<n;j++)for(k=g[j];k;k=nxt[k])if(w[v[k]]&&i>w[v[k]])f[i-w[v[k]]][v[k]]+=c[j]*d[j];
}
return printf("%.8f",ans),0;
}


转载于:https://www.cnblogs.com/clrs97/p/5095714.html
展开全文 • 有一个吸血鬼被困了，有n条路可以逃出去，每条路有一个难度c[],他初始的战斗力是f，对于第i条路，若f > c[i]他花t[i]天就能出去，否则，他就停留一天，同时战斗力增加c[i]然后再选...dp[i] = 1/n * t[j]（c[j] > i），d

题意：

有一个吸血鬼被困了，有n条路可以逃出去，每条路有一个难度c[],他初始的战斗力是f，对于第i条路，若f > c[i]他花t[i]天就能出去，否则，他就停留一天，同时战斗力增加c[i]然后再选一条路走出去，他走每条路的概率是相同的。问他逃出去的天数的期望。

设dp[i]表示在战斗力为i时逃出去的期望值，那么可推出状态方程

dp[i] = 1/n * t[j]（c[j] > i），dp[i] = 1/n * (1+dp[ i+c[j] ] )( c[j] <= i)。

需要注意的是终态的确定。当f > Max时，这时的期望值为总时间的平均值便是终态了，但是i + c[j]有可能大于Max+1，（也就是f最大为Max）所以终态应该是Max*2。初始化时就忘乘2了。

还有就是t[i]是整数。

自己总是不知道到底让dp表示什么好。。。。

Description

Background
If thou doest well, shalt thou not be accepted? and if thou doest not well, sin lieth at the door. And unto thee shall be his desire, and thou shalt rule over him.
And Cain talked with Abel his brother: and it came to pass, when they were in the field, that Cain rose up against Abel his brother, and slew him.
And the LORD said unto Cain, Where is Abel thy brother? And he said, I know not: Am I my brother's keeper?
And he said, What hast thou done? the voice of thy brother's blood crieth unto me from the ground.
And now art thou cursed from the earth, which hath opened her mouth to receive thy brother's blood from thy hand;
When thou tillest the ground, it shall not henceforth yield unto thee her strength; a fugitive and a vagabond shalt thou be in the earth.

—— Bible Chapter 4
Now Cain is unexpectedly trapped in a cave with N paths. Due to LORD's punishment, all the paths are zigzag and dangerous. The difficulty of the ith path is ci.
Then we define f as the fighting capacity of Cain. Every day, Cain will be sent to one of the N paths randomly.
Suppose Cain is in front of the ith path. He can successfully take ti days to escape from the cave as long as his fighting capacity f is larger than ci. Otherwise, he has to keep trying day after day. However,
if Cain failed to escape, his fighting capacity would increase ci as the result of actual combat. (A kindly reminder: Cain will never died.)
As for ti, we can easily draw a conclusion that ti is closely related to ci. Let's use the following function to describe their relationship: After D days, Cain finally escapes from the cave. Please output the expectation of D.

Input

The input consists of several cases. In each case, two positive integers N and f (n ≤ 100, f ≤ 10000) are given in the first line. The second line includes N positive integers ci (ci ≤ 10000,
1 ≤ i ≤ N)

Output

For each case, you should output the expectation(3 digits after the decimal point).

Sample Input

3 1
1 2 3

Sample Output

6.889

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstring>
using namespace std;
double dp;
int b;
double a=(1+sqrt(5))*0.5;
int main()
{
int n,f;
while(~scanf("%d %d",&n,&f))
{
int Max=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&b[i]);
Max=max(Max,b[i]);
}
memset(dp,0,sizeof(dp));
for(int i=2*Max; i>=f; i--)
{
dp[i]=0;
for(int j=1; j<=n; j++)
{
if(i>b[j])dp[i]+=(int)(a*b[j]*b[j]);
else dp[i]+=(1+dp[i+b[j]]);
}
dp[i]/=n;
}
printf("%.3lf\n",dp[f]);
}
return 0;
}递归方法，觉得还是这个方法好理解#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#define ll long long
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int MAXN=1000010;
const double op=(1.0+sqrt(5))/2;
double dp[MAXN];
bool vis[MAXN];
int n;
int c;
double dfs(int u)
{
if(vis[u])
return dp[u];
vis[u]=1;
dp[u]=0;
for(int i=0;i<n;i++)
{
if(c[i]<u)
{
double temp=op*c[i]*c[i]*1.0;
int t=(int)temp;
dp[u]+=1.0*t/n;
}
else
dp[u]+=(1+dfs(u+c[i]))/n*1.0;
}
return dp[u];
}
int main()
{
int f,i;
while(scanf("%d%d",&n,&f)==2)
{
for(i=0;i<n;i++)
scanf("%d",&c[i]);
memset(vis,0,sizeof(vis));
double ans=dfs(f);
printf("%.3f\n",ans);
}
return 0;
}

展开全文 • dp[i][j] = Σ dp[i+val[i]][k]/d[k] 将第一维看做层次 那么同层之间需要高斯消元解决 对每一层都做一次是 hp*n^3 但是不同层次之间只有常数列是不一样的 记录第一次将系数矩阵消成上三角矩阵的过程 ...
• #include using namespace std; double dp[20000+10]; int t,f,k,mx,c;int main() { int n; while(~scanf("%d%d",&n,&f)) { mx=0; for(int i=0;i;i++)
• 一个比较显然的式子是f(i,j)=∑(j,v)∈Ef(i+a(j),v)d(v)f(i,j)=\sum\limits_{(j,v)\in E}{f(i+a(j),v)\over d(v)} 但是有一个问题就是如果a(j)=0的话f(i+a(j))实际上还没有推出来，和f(i)是同一层的 那么就需要用...
• 我们有比较显然的期望dp，f[x][i]表示到x点血量为i的期望次数。 我们有转移f[x][i]=∑yf[y][i+w[x]]du[y]f[x][i]=∑yf[y][i+w[x]]du[y]f[x][i]=\sum_y\frac{f[y][i+w...由于血量不增，因此我们可以按剩余血量分层d...
• 题目链接： ... 题目大意: 有n条路，选每条路的概率相等，初始能力值为f,每条路通过的难度值为ci,当能力值大于某条路A的难度值b时，能够成功逃离，花费时间ti,小于等于时，不能逃离但能力值增加b. ...简单期望d
• net/http.(*conn).serve(0xc00024e500, 0x47d3640, 0xc00022e2c0) /usr/local/go/src/net/http/server.go:1878 +0x851 created by net/http.(*Server).Serve /usr/local/go/src/net/http/server.go:2884 +...
• ugw系统运行过程会生成大量的log，包括pad log , Mcafee log , Hub log. ...1. 使用curl实现，返回值如下{"code":"0","file_name":"static/lxw/test/1000004/ugw_028d3640aae5_20170928170415_log.tar.gz"}200
• github.com/spf13/cobra.(*Command).execute(0xc4200d7440, 0xc4202d3640, 0x1, 0x1, 0xc4200d7440, 0xc4202d3640) /build/erwan/src/github.com/spf13/cobra/command.go:704 +0x2c6 github.com/spf13/cobra.(*...
• 网易开源的airtest库，本身上是一个python第三方库，而他的airtestIDE则是一个强大的集成工具。 ...https://www.jianshu.com/p/e62d3640c07c 先介绍三者： 1、airtest是最近流行的游戏UI测...
• <p><img alt="ie11-webgl-canvas" src="https://img-blog.csdnimg.cn/img_convert/c463abd38fa04457c31d3640dc3a0ad1.png" /></p> <p>This can be attributed to IE's incomplete WebGL support. The error ...
• <div><p>Expected: Clicking...<p><img alt="image" src="https://img-blog.csdnimg.cn/img_convert/a10ac53d3640fd66dba5df35d161c8d2.png" /></p><p>该提问来源于开源项目：learningequality/ka-lite</p></div>
• (203, 'task2', ' madvi ', 'vadodara', 'Gujarat', 'India', 22.302665500000, 73.204284700000, 0x000000000101000000af642200134d5240a320787c7b4d3640), (204, 'task3', 'panigat ', 'vadodara', 'Gujarat', '... mysql php
• <p><img width="396" alt="count" src="https://img-blog.csdnimg.cn/img_convert/3af6f2035021885b172f0d3640fbc79d.png" /></p> <p>Rejection details: <p><img width="701" alt="reject" src=...
• 0x00007f61957d3640: 0000000000000000 00007f61c83fc800 0x00007f61957d3650: 0000000000000704 0000000000000006 0x00007f61957d3660: 0000000000000001 00007f6100000000  <p>Instructions: (pc&#... centos java 有问必答
• overlay 1865344 117269 1748075 7% /run/k3s/containerd/io.containerd.runtime.v2.task/k8s.io/091c48a0ca458a64622ef067b0c95866fed75b648d3640c6f3ff18f26d9e5c0c/rootfs shm 485303 1 485302 1% /run/k3s/...
• </code> (#5897)</li><li><a href="https://urls.greenkeeper.io/zeit/next.js/commit/cd1d3640a9abfa3df3cadf712fe095aa5326a089"><code>cd1d364</code></a> <code>Improve with-sentry example (#5727)</code></li...
• #6 0x0000563f1d3640a9 n/a (ghb + 0x2220a9) #7 0x0000563f1d345946 n/a (ghb + 0x203946) #8 0x0000563f1d31faf9 ghb_backend_init (ghb + 0x1ddaf9) #9 0x0000563f1d30c958 ghb_activate_cb (ghb...
• 28 CoreFoundation 0x00000001858d3640 ___CFXNotificationPost_block_invoke + 56 29 CoreFoundation 0x0000000185951024 -[_CFXNotificationRegistrar find:object:observer:enumerator:] + 1404 30 Core...
• segfault at 0 ip 00007f98d3640c57 sp 00007f98a5ffaa98 error 6 in libc-2.17.so[7f98d34f7000+1b6000] segfault at 0 ip 00007f762d4a0c57 sp 00007f75ffffea98 error 6 in libc-2.17.so[7f762d357000+1b...
• └─parrot_cvmfs_st,21378 -d all -o /scratch365/khurtado/myglidein_test4/parrot301_t3_d12chas_dot_21358.debug -M/cvmfs/cms.cern.ch/SITECONF/local=/scratch365/khurtado/myglidein_te └─6,21379 ./...
• Ubuntu 20.04.2 设置程序开机自启动 Ubuntu 20.04.2 设置程序开机自启动 ...root@dell3640:/home/uadmin/huimv.hy# cd /etc/profile.d root@dell3640:/etc/profile.d# ll total 64 drwxr-xr-x 2 root root 4096 Ma linux jar java ubuntu
• http://cache.baiducontent.com/c?m=9d78d513d98002b8599dcb201a17a7374408c6347691c4523f8a9c12d52219564615fea6777c4d51c4c50b3640f9154bea876a25711e71edcc94d61781ee912828822529235cc01a438d4eb29d1163927bce1b...  ...