2015
04-13

# 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

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]);
}


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。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。