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

给出 n 条路，然后每条路有一个c[i]的困难值 和 t[i] 的逃脱天数，一个人的战斗力是 f ，当战斗力大于 c[i] 时， 花t[i]天逃出去，否则下一天随机到另一个地方， 问你这个人期望的走出去的天数是几天。
一开始考虑 dp[i][j] 表示从第 i 个位置出发，战斗力为 j 时的期望逃脱天数。这样可以得到：
1. j > c[i], dp[i][j] = t[i]
2. j <= c[i], dp[i][j] = Σ(dp[k][j+c[i]] + 1) / n
然后去枚举开始的位置，并加上记忆化搜索，感觉是可以的，但是这样做会 T 。
 /*

           .

          ';;;;;.

         '!;;;;;;!;`

        '!;|&#@|;;;;!:

       `;;!&####@|;;;;!:

      .;;;!&@$$%|!;;;;;;!'.`:::::'.

      '!;;;;;;;;!$@###&|;;|%!;!$|;;;;|&&;.

      :!;;;;!$@&%|;;;;;;;;;|!::!!:::;!$%;!$%`    '!%&#########@$!:.

      ;!;;!!;;;;;|$$&@##$;;;::'''''::;;;;|&|%@$|;;;;;;;;;;;;;;;;!$;

      ;|;;;;;;;;;;;;;;;;;;!%@#####&!:::;!;;;;;;;;;;!&####@%!;;;;$%`

     `!!;;;;;;;;;;!|%%|!!;::;;|@##%|$|;;;;;;;;;;;;!|%$#####%;;;%&;

     :@###&!:;;!!||%%%%%|!;;;;;||;;;;||!$&&@@%;;;;;;;|$$##$;;;%@|

     ;|::;;;;;;;;;;;;|&&$|;;!$@&$!;;;;!;;;;;;;;;;;;;;;;!%|;;;%@%.

    `!!;;;;;;;!!!!;;;;;$@@@&&&&&@$!;!%|;;;;!||!;;;;;!|%%%!;;%@|.

 %&&$!;;;;;!;;;;;;;;;;;|$&&&&&&&&&@@%!%%;!||!;;;;;;;;;;;;;$##!

 !%;;;;;;!%!:;;;;;;;;;;!$&&&&&&&&&&@##&%|||;;;!!||!;;;;;;;$&:

 ':|@###%;:;;;;;;;;;;;;!%$&&&&&&@@$!;;;;;;;!!!;;;;;%&!;;|&%.

  !@|;;;;;;;;;;;;;;;;;;|%|$&&$%&&|;;;;;;;;;;;;!;;;;;!&@@&'

   .:%#&!;;;;;;;;;;;;;;!%|$$%%&@%;;;;;;;;;;;;;;;;;;;!&@:

   .%$;;;;;;;;;;;;;;;;;;|$$$$@&|;;;;;;;;;;;;;;;;;;;;%@%.

     !&!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;|@#;

      `%$!;;;;;;;;;;;$@|;;;;;;;;;;;;;;;;;;;;;;;;!%$@#@|.

        .|@%!;;;;;;;;;!$&%||;;;;;;;;;;;;;;;;;!%$$$$$@#|.

            ;&$!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%#####|.

            |##$|!;;;;;;::'':;;;;;;;;;;;;;!%$$$@#@;

           ;@&|;;;;;;;::'''''':;;;;;;;|$&@###@|`

         .%##@|;;;;:::''''''''''::;!%&##$'

       `$##@$$@@&|!!;;;:'''''::::;;;;;|&#%.

     ;&@##&$%!;;;;;;::''''''''::;!|%$@#@&@@:

      .%@&$$|;;;;;;;;;;:'''':''''::;;;%@#@@#%.

     :@##@###@$$$$$|;;:'''':;;!!;;;;;;!$#@@#$;`

      `%@$$|;;;;;;;;:'''''''::;;;;|%$$|!!&###&'

      |##&%!;;;;;::''''''''''''::;;;;;;;!$@&:`!'

     :;!@$|;;;;;;;::''''''''''':;;;;;;;;!%&@$:                 !@#$'

       |##@@&%;;;;;::''''''''':;;;;;;;!%&@#@$%:              '%%!%&;

       |&%!;;;;;;;%$!:''''''':|%!;;;;;;;;|&@%||`            '%$|!%&;

       |@%!;;!!;;;||;:'''''':;%$!;;;;!%%%&#&%$&:           .|%;:!&%`

       !@&%;;;;;;;||;;;:''::;;%$!;;;;;;;|&@%;!$;          `%&%!!$&:

       '$$|;!!!!;;||;;;;;;;;;;%%;;;;;;;|@@|!$##;         !$!;:!$&:

        |#&|;;;;;;!||;;;;;;;;!%|;;;;!$##$;;;;|%'      `%$|%%;|&$'

         |&%!;;;;;;|%;;;;;;;;$$;;;;;;|&&|!|%&&;  .:%&$!;;;:!$@!

         `%#&%!!;;;;||;;;;;!$&|;;;!%%%@&!;;;!!;;;|%!;;%@$!%@!

         !&!;;;;;;;;;||;;%&!;;;;;;;;;%@&!;;!&$;;;|&%;;;%@%`

        '%|;;;;;;;;!!|$|%&%;;;;;;;;;;|&#&|!!||!!|%$@@|'

        .!%%&%'`|$;       :|$#%|@#&;%#%.

 */

 #include <map>

 #include <set>

 #include <list>

 #include <ctime>

 #include <cmath>

 #include <stack>

 #include <queue>

 #include <string>

 #include <vector>

 #include <cstdio>

 #include <bitset>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define  lowbit(x)  x & (-x)

 #define  mes(a, b)  memset(a, b, sizeof a)

 #define  fi         first

 #define  se         second

 #define  pii        pair<int, int>

 #define  INOPEN     freopen("in.txt", "r", stdin)

 #define  OUTOPEN    freopen("out.txt", "w", stdout)

 typedef unsigned long long int ull;

 typedef long long int ll;

 const int    maxn = 1e2 + ;

 const int    maxm = 2e4 + ;

 const int    mod  = 1e9 + ;

 const ll     INF  = 1e18 + ;

 const int    inf  = 0x3f3f3f3f;

 const double pi   = acos(-1.0);

 const double eps  = 1e-;

 using namespace std;

 int n, m;

 int cas, tol, T;

 int c[maxn];

 int t[maxn];

 double dp[maxn][maxm];

 void init() {

     mes(c, );

     mes(t, );

     mes(dp, );

 }

 void dfs(int id, int f) {

     if(dp[id][f])    return ;

     if(f > c[id]) {

         dp[id][f] = 1.0 * t[id];

         return ;

     }

     double ans = 0.0;

     for(int i=; i<=n; i++) {

         dfs(i, f+c[id]);

         ans += dp[i][f+c[id]] + 1.0;

     }

     dp[id][f] = ans / n;

 }

 int main() {

     while(~scanf("%d%d", &n, &m)) {

         init();

         for(int i=; i<=n; i++) {

             scanf("%d", &c[i]);

             t[i] = (int)((1.0 + sqrt(5.0)) /  * c[i] * c[i]);

         }

         double ans = 0.0;

         for(int i=; i<=n; i++) {

             dfs(i, m);

             ans += dp[i][m];

         }

         printf("%.3f\n", ans / n);

     }

     return ;

 }

TLE

观察方程发现 dp[i][j] 的 i 每次都要去重复枚举，花费了太多的时间，那么想办法优化掉一维。
dp[i] 表示战斗力为 i 时的期望天数。
然后再去搜索每条路
1. i > c[j], dp[i] += t[j]
2. i <= c[j], dp[i] += dp[i + c[j]] + 1
然后在记忆化搜索，就能过了....
 /*

           .

          ';;;;;.

         '!;;;;;;!;`

        '!;|&#@|;;;;!:

       `;;!&####@|;;;;!:

      .;;;!&@$$%|!;;;;;;!'.`:::::'.

      '!;;;;;;;;!$@###&|;;|%!;!$|;;;;|&&;.

      :!;;;;!$@&%|;;;;;;;;;|!::!!:::;!$%;!$%`    '!%&#########@$!:.

      ;!;;!!;;;;;|$$&@##$;;;::'''''::;;;;|&|%@$|;;;;;;;;;;;;;;;;!$;

      ;|;;;;;;;;;;;;;;;;;;!%@#####&!:::;!;;;;;;;;;;!&####@%!;;;;$%`

     `!!;;;;;;;;;;!|%%|!!;::;;|@##%|$|;;;;;;;;;;;;!|%$#####%;;;%&;

     :@###&!:;;!!||%%%%%|!;;;;;||;;;;||!$&&@@%;;;;;;;|$$##$;;;%@|

     ;|::;;;;;;;;;;;;|&&$|;;!$@&$!;;;;!;;;;;;;;;;;;;;;;!%|;;;%@%.

    `!!;;;;;;;!!!!;;;;;$@@@&&&&&@$!;!%|;;;;!||!;;;;;!|%%%!;;%@|.

 %&&$!;;;;;!;;;;;;;;;;;|$&&&&&&&&&@@%!%%;!||!;;;;;;;;;;;;;$##!

 !%;;;;;;!%!:;;;;;;;;;;!$&&&&&&&&&&@##&%|||;;;!!||!;;;;;;;$&:

 ':|@###%;:;;;;;;;;;;;;!%$&&&&&&@@$!;;;;;;;!!!;;;;;%&!;;|&%.

  !@|;;;;;;;;;;;;;;;;;;|%|$&&$%&&|;;;;;;;;;;;;!;;;;;!&@@&'

   .:%#&!;;;;;;;;;;;;;;!%|$$%%&@%;;;;;;;;;;;;;;;;;;;!&@:

   .%$;;;;;;;;;;;;;;;;;;|$$$$@&|;;;;;;;;;;;;;;;;;;;;%@%.

     !&!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;|@#;

      `%$!;;;;;;;;;;;$@|;;;;;;;;;;;;;;;;;;;;;;;;!%$@#@|.

        .|@%!;;;;;;;;;!$&%||;;;;;;;;;;;;;;;;;!%$$$$$@#|.

            ;&$!;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;%#####|.

            |##$|!;;;;;;::'':;;;;;;;;;;;;;!%$$$@#@;

           ;@&|;;;;;;;::'''''':;;;;;;;|$&@###@|`

         .%##@|;;;;:::''''''''''::;!%&##$'

       `$##@$$@@&|!!;;;:'''''::::;;;;;|&#%.

     ;&@##&$%!;;;;;;::''''''''::;!|%$@#@&@@:

      .%@&$$|;;;;;;;;;;:'''':''''::;;;%@#@@#%.

     :@##@###@$$$$$|;;:'''':;;!!;;;;;;!$#@@#$;`

      `%@$$|;;;;;;;;:'''''''::;;;;|%$$|!!&###&'

      |##&%!;;;;;::''''''''''''::;;;;;;;!$@&:`!'

     :;!@$|;;;;;;;::''''''''''':;;;;;;;;!%&@$:                 !@#$'

       |##@@&%;;;;;::''''''''':;;;;;;;!%&@#@$%:              '%%!%&;

       |&%!;;;;;;;%$!:''''''':|%!;;;;;;;;|&@%||`            '%$|!%&;

       |@%!;;!!;;;||;:'''''':;%$!;;;;!%%%&#&%$&:           .|%;:!&%`

       !@&%;;;;;;;||;;;:''::;;%$!;;;;;;;|&@%;!$;          `%&%!!$&:

       '$$|;!!!!;;||;;;;;;;;;;%%;;;;;;;|@@|!$##;         !$!;:!$&:

        |#&|;;;;;;!||;;;;;;;;!%|;;;;!$##$;;;;|%'      `%$|%%;|&$'

         |&%!;;;;;;|%;;;;;;;;$$;;;;;;|&&|!|%&&;  .:%&$!;;;:!$@!

         `%#&%!!;;;;||;;;;;!$&|;;;!%%%@&!;;;!!;;;|%!;;%@$!%@!

         !&!;;;;;;;;;||;;%&!;;;;;;;;;%@&!;;!&$;;;|&%;;;%@%`

        '%|;;;;;;;;!!|$|%&%;;;;;;;;;;|&#&|!!||!!|%$@@|'

        .!%%&%'`|$;       :|$#%|@#&;%#%.

 */

 #include <map>

 #include <set>

 #include <list>

 #include <ctime>

 #include <cmath>

 #include <stack>

 #include <queue>

 #include <string>

 #include <vector>

 #include <cstdio>

 #include <bitset>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define  lowbit(x)  x & (-x)

 #define  mes(a, b)  memset(a, b, sizeof a)

 #define  fi         first

 #define  se         second

 #define  pii        pair<int, int>

 #define  INOPEN     freopen("in.txt", "r", stdin)

 #define  OUTOPEN    freopen("out.txt", "w", stdout)

 typedef unsigned long long int ull;

 typedef long long int ll;

 const int    maxn = 1e2 + ;

 const int    maxm = 1e5 + ;

 const int    mod  = 1e9 + ;

 const ll     INF  = 1e18 + ;

 const int    inf  = 0x3f3f3f3f;

 const double pi   = acos(-1.0);

 const double eps  = 1e-;

 using namespace std;

 int n, m;

 int cas, tol, T;

 int c[maxn];

 int t[maxn];

 double dp[maxm];

 void init() {

     mes(c, );

     mes(t, );

     mes(dp, );

 }

 void dfs(int f) {

     if(dp[f])

         return ;

     double ans1 = 0.0;

     double ans2 = 0.0;

     for(int i=; i<=n; i++) {

         if(f > c[i]) {

             ans1 += 1.0 * t[i];

         } else {

             dfs(f+c[i]);

             ans2 += dp[f+c[i]];

             ans2 += 1.0;

         }

     }

     dp[f] = (ans1 + ans2) / n;

 }

 int main() {

     while(~scanf("%d%d", &n, &m)) {

         init();

         for(int i=; i<=n; i++) {

             scanf("%d", &c[i]);

             t[i] = (int)((1.0 + sqrt(5.0)) /  * c[i] * c[i]);

         }

         dfs(m);

         printf("%.3f\n", dp[m]);

     }

     return ;

 }

AC

最新文章

  1. HBase完全分布模式安装
  2. js 客户端如何判断浏览器是否暗转Flash
  3. python tornado框架实现CRUD
  4. CharsetUtils.java
  5. Use jQuery to hide a DIV when the user clicks outside of it
  6. iOS 8 Xcode6 设置Launch Image 启动图片&lt;转&gt;
  7. Qt编程之QString 处理换行
  8. swift中通知的使用
  9. su命令详解
  10. 简单易懂的 Vue.js 基础知识 ！
  11. 【译】快速起步-JSX简介
  12. curl不能支持https问题
  13. fixed不能罩住下面的内容
  14. Triangle2D类（Java）
  15. 图学ES6-2.let与const命令
  16. 【Unity】7.1 Input类的方法和变量
  17. sqlite的一个Unable to Open database file的坑爹错误
  18. H.264 White Paper学习笔记（二）帧内预测
  19. 2016NOI冬令营day4
  20. Swift 编程语言入门教程

热门文章

  1. Android Studio调试手机或者安装APK的时候出现install failed test only
  2. C# 仿360悬浮球开发demo程序
  3. ASP.NET Core 入门教程 8、ASP.NET Core + Entity Framework Core 数据访问入门
  4. python实例七
  5. JS时间的获取及格式
  6. LeetCode算法题-Number Complement（Java实现-五种解法）
  7. 阿里巴巴JAVA开发手册
  8. 英语进阶系列-A06-本周总结
  9. kernel笔记——内核同步与锁
  10. echarts堆叠图添加总量