Topcoder SRM536 div2 1000pt

此题乃dp！先排个序，dp[ x ][ y ]每次记录合并 X 次把前 Y 个公司全部合并所能长生的最大利润，有点贪心的思想，贪心确实是成立的，合并每个公司相当于对每个公司附一个权值，由于是算他们的算术平均数，那么先和并的公司最后附上的那个等价的权值就一定是最小的，而我一开始已经对利润排了序，说明最后利润低的公司的权值一定不大于利润高的公司，而恰恰最优解也一定是利润低的公司权值低，利润高的公司权值高，那么这种贪心则必然是正确的！

然后是一个动态规划过程，算出每个dp[ x ][ y ]，时间复杂度是O(n3)，对于dp[x][y] 一定是某个 dp[x-1][??] 变化过来的，所以枚举所有的合并 x-1次且再合并一次达到y的所有可行情况，取利润最大的赋给dp[x][y]，哎，想到的时候只有5分钟了，在亢奋状态下APM全面爆发，结果编译没通过！devtang在旁边悠哉的说，少年别紧张，还有5秒。。fuck，没希望了！T T！fuck！！再给我10分钟就好。。。%>_<%

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;

#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif

#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a)         for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a)        for( int i = (a)-1 ; i >= 0 ; i --)
#define S64(a)          scanf(in64,&a)
#define SS(a)           scanf("%d",&a)
#define LL(a)           ((a)<<1)
#define RR(a)           (((a)<<1)+1)
#define SZ(a)           ((int)a.size())
#define PP(n,m,a)       puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
#define pb              push_back
#define CL(Q)           while(!Q.empty())Q.pop()
#define MM(name,what)   memset(name,what,sizeof(name))
#define read            freopen("in.txt","r",stdin)
#define write           freopen("out.txt","w",stdout)

const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-10;
const double pi = acos(-1.0);
const int maxn = 111;
double dp[maxn][maxn];
double sum[maxn][maxn];
int n;
int s[maxn];
int a[maxn];
struct MergersDivTwo
{
	double findMaximum(vector <int> v, int k)
	{
		n = v.size();
		sort(v.begin(),v.end());
		for(int i=1;i<=n;i++)
		{
			a[i] = v[i-1];
		}
		MM(s,0);
		MM(sum,0);
		FOR(i,1,n)
		{
			s[i] = s[i-1] + a[i];	
		}
		FOR(i,1,n) FOR(j,i,n)
		{
			sum[i][j] = s[j] - s[i-1];
		}
		FF(i,maxn) FF(j,maxn)
		{
			dp[i][j] = -oo;
		}		
		for(int i=1;i<=n;i++)
		{
			double di=i;
			if(i>=k)
			{
				dp[1][i] = sum[1][i]/di;
			}
		}
		int mt = (n-1)/(k-1);
		int mi;
		int mm;
		double temp,t2;
		FOR(i,2,mt)
		{
			mi = (k-1)*(i-1)+1;
			mm = (k-1)*i+1;
			FOR(j,1,n)
			{
				if(j < mm)
				{
					continue;
				}				
				temp = -oo;
				FOR(u,mi,j)
				{
					if(j-u+1 >= k && u >= mi)
					{
						t2 = ( dp[i-1][u] + sum[u+1][j] )/ double(j-u+1);
						temp = temp > t2 ? temp : t2;	
					}						
				}	
				dp[i][j] = temp;					
			}
		}
		double ans=-oo;
		FOR(i,1,n)
		{
			ans = max(ans,dp[i][n]);	
		}
		return ans;		
	}
};