Description
炸弹是塔利班对付美军的武器之一。默罕默德在塔利班的主要任务是做炸弹。默罕默德所做的新型炸弹由若干个小炸弹组成，每个小炸弹有一个威力值，整个炸弹的威力值是组成这个炸弹的最大威力差的平方，即(max-min)^2，假设一个炸弹有5个小炸弹组成，威力分别为5 9 8 2 1，那么它的威力为(9-1)^2=64。 时间紧任务多默罕默德的师傅兼老爸老默罕默德又不在，默罕默德不敢调整小炸弹的顺序，只能确定它们的分组。请你帮助默罕默德确定小炸药的分组，使制造出的炸弹拥有最大的威力和。
Input
第一行有 1 个正整数N( 1 <= N <= 1000)，表示有N个小炸弹。 第二行有N个数，其中第i个数Ai表示第i个小炸弹的威力值( 0 <= Ai <= 1000)。
Output
输出炸弹的威力和。
Sample Input
6 5 9 8 2 1 6
Sample Output
77
思路：
题意是不能改变炸弹顺序，只能确定它们的分组，使制造出的炸弹拥有最大的威力和。
方便理解题意，那么先看下样例是怎么过的
5 9 8 2 1 6
一组数据有多种分法:
你可以分成1组，那么威力和就是只分成一组的威力（9-1）²=64。
也可以分成2组，如（5，9） （8，2，1，6）这样威力和是16+49=65，分成2组还有别的组合这里就不算了。
我们可以知道6个数 最多能分成6组（每个数为一组）。
样例的最优分组是 (5,9) (8,2) (1,6)。3组,这样威力和是16+35+25=77最大。
开始分析 :看上去，好像能用暴力，但是仔细分析就觉得不靠谱了。1000个数就有
C(0,999)+C(1,999)+C(2,999)+……+C（999，999）种可能。这就只能呵呵了。
换种思路：
有n个小炸弹 可以能分成i组（1<=i<=n）。
如果我们已经知道（1<=i<=n）dp[i][n]表示：n个小炸弹,分成i组的各种组合中，（威力和最大的那个组合）的（威力和）。如样例中dp[1][6]=64 . dp[3][6]=77.
那么我只要输出(1<=i<=n）中dp[i][n]最大的那个就行了。
那么现在的问题变成如何求dp[i][n].想到这里已经明白显然是个动态规划问题，要去想如何进行状态转移。
dp[i][n]讨论的是把n个数分成i组的问题。为了方便说明，继续拿样例讨论。
比如 5 9 8 2 1 6 求dp[3][6].此时我们已经算出最优解的情况是(5,9) (8,2) (1,6). 这时最后一组是(1，6)
但是一开始我不知道最优解的最后一组是6，还是（1,6）,还是(2,1,6)等。
为什么要知道最后一组呢？
假设最后一组是6，那么问题就变成求5 9 8 2 1中分成2组的最大威力和了。
此时他的威力和是 dp[2][5]+v[6][6]. //假设我们已经知道v[i][j]代表下标i到j为一组的威力和.
同理一样如果最后一组是（1，6）,那么问题就变成求5,9,8,2中分成2组的最大威力和。
此时他的威力和是dp[2][4]+v[5][6],
我们只要枚举这样所有的可能，就能找出最优解得到dp[3][6]。
我们知道,若最后一组知道，那么扣掉最后一组的数，假设还剩k个数，k显然不能等于n.
这k个数要分成i-1组显然k要大于i-1。那么i-1<=k<n.
此时已经可以推出转移方程：dp[i][j]=max(dp[i][j],dp[i-1][k]+v[k+1][j]); (i-1<=k<n)
剩下的把v[i][j]搞定就好了。
#include <cstdio> #include <algorithm> using namespace std; #define max(a,b) (((a)>(b))?(a):(b)) int n,a[1005],dp[1005][1005],v[1005][1005]; int main() { int i,j,k,res; int iMax,iMin; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<=n;i++) { iMax=iMin=a[i]; for(j=i;j<=n;j++) { if(a[j]>iMax) iMax=a[j]; if(a[j]<iMin) iMin=a[j]; v[i][j]=(iMax-iMin)*(iMax-iMin); } }//v[i][j]代表从下标i到j为一组的炸弹威力 //dp i=1; for(j=1;j<=n;j++) dp[1][j]=v[1][j]; // i>=2; for(i=2;i<=n;i++) { for(j=i;j<=n;j++) { for(k=i-1;k<j;k++) { dp[i][j]=max(dp[i][j],dp[i-1][k]+v[k+1][j]); } } } res=0; for(i=1;i<=n;i++) { res=max(res,dp[i][n]); } printf("%d\n",res); return 0; }