URAL 1776 C

点击打开链接

题意：

要把1-n个火箭都点火，其中每次点火间隔10s.

点火步骤：1、首先点燃第一个和最后一个2、点燃任意两个已点火箭的中间一个。注意可以有多个区间，每次可以同时点燃多个。

求点燃所有火箭的时间的期望。

思路：

首先，期望取最大值这个是错误的

这个dp[i][j]应该表示长度为i的，放j个火箭的概率是多少

直接dfs解决就好了【dalao专用：直接什么什么就好了，很显然巴拉巴拉巴拉....】

并不会，也不是很理解...

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define mem(a) memset(a,0,sizeof(a))
 5 #define mp(x,y) make_pair(x,y)
 6 const int maxn = 400+10;
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 
17 double dp[maxn][maxn];
18 int vis[maxn][maxn];
19 
20 double dfs(int x,int y){
21     if(vis[x][y]) return dp[x][y];
22     if(x==0) return 1.0;
23     if(y==0) return 0.0;
24     double p = 1.0/x;
25     double ans = 0;
26     for(int k=1; k<=x; k++)
27         ans += p * dfs(k-1,y-1) * dfs(x-k,y-1);
28     vis[x][y] = 1;
29     return dp[x][y] = ans;
30 }
31 
32 int main(){
33     int n = read();
34     double ans = 0;
35     mem(dp),mem(vis);
36     for(int i=1; i<=n-2; i++)
37         ans += (dfs(n-2,i)-dfs(n-2,i-1)) * i*10;
38     printf("%.10lf
",ans);
39 
40     return 0;
41 }
42 
43 //https://vjudge.net/contest/87643#problem/C