首页 > ACM题库 > HDU-杭电 > HDU 3815-Stones-动态规划-[解题报告]HOJ
2015
04-13

HDU 3815-Stones-动态规划-[解题报告]HOJ

Stones

问题描述 :

There are N piles of stones on the desk at the beginning and N -1 rounds follows. For each round, two piles are chosen at random and we merge them into a new pile. If the new pile has K stones, then we will get K*K points.
For example, there are three piles of stones and they have 2, 5 and 4 stones respectively. If in the first round we merge the first pile and the third pile, a new pile with 6 stones are created and we will get 6*6=36 points. The second round we will create a new pile with 11 stones and get 121 points. Now we get 157 points in total. Similarly, we will get 170 points if we merge the first pile and the second pile and will get 202 points if we merge the second pile and third pile. The expected points we will get is (157+170+202)/3 = 176.333333.
Your task it to compute the expected points we will get after N-1 rounds.

输入:

The first line contains an integer T indicating the number of test cases.
The first line of each test case contains an integer N indicating the number of piles. The second line contains N integers Ai indicating the size of each pile.

Technical Specification
1. 1<=T<=50
2. 1<=N <=100
3. 1<=Ai<=1000

输出:

The first line contains an integer T indicating the number of test cases.
The first line of each test case contains an integer N indicating the number of piles. The second line contains N integers Ai indicating the size of each pile.

Technical Specification
1. 1<=T<=50
2. 1<=N <=100
3. 1<=Ai<=1000

样例输入:

3
1
100
2
3 4
3
2 5 4

样例输出:

Case 1: 0.00
Case 2: 49.00
Case 3: 176.33

题意:有n个小球,m个盒子,小球被分配到1到m-1的盒子中,每次P选定其中的一部分小球,C可以选择保留或不保留选定的球,若保留,这些球都向移动到其右边的盒子,剩下的剔除,反之亦然。如果有球到m盒子时P就赢了。问C赢的话,开局的方式有多少种。

思路:如果一种局面使得C必胜时,从左往右计数球的个数,将每个盒子中的球数除以2,折算到它右边的盒子中,最终使得m盒子没有球的情况,就是C必胜的情况。这个想法是从4 1 0 和4 2 0 这种情况考虑发现的。

          dp[m][n][k]表示到第m个格子,用了n个球,且第m个格子折算后的数为k的情况数量。

AC代码如下:

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll dp[110][210][410],MOD=1e9+7;
int main()
{ int i,j,k,n,m;
  dp[0][0][0]=1;
  for(i=1;i<=100;i++)
   for(j=0;j<=200;j++)
   { dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])%MOD;
     for(k=0;k<=200;k++)
      dp[i][j][k]=(dp[i][j-1][k-1]+dp[i-1][j][k*2]+dp[i-1][j][k*2+1])%MOD;
   }
  while(~scanf("%d%d",&n,&m))
   printf("%lld\n",dp[m][n][0]);
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/u014733623/article/details/38963067


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。