FZOJ 2014年11月份月賽 ytaaa（dp + RMQ）
題目鏈接：http://acm.fzu.edu.cn/contest/problem.php?cid=140&sortid=3
Problem Description
Ytaaa作為一名特工執行了無數困難的任務，這一次ytaaa收到命令，需要炸毀敵人的一個工廠，為此ytaaa需要制造一批炸彈以供使用。 Ytaaa使用的這種新型炸彈由若干個炸藥組成，每個炸藥都有它的威力值，而炸彈的威力值為組成這個炸彈的所有炸藥的最大威力差的平方，即(max-min)^2，假設一個炸彈有5個炸藥組成，威力分別為5 9 8 2 1，那麼它的威力為(9-1)^2=64。現在在炸彈的制造流水線上已經有一行n個炸藥，由於時間緊迫，ytaaa並沒有時間改變它們的順序，只能確定他們的分組。作為ytaaa的首席顧問，請你幫助ytaaa確定炸藥的分組，使制造出的炸彈擁有最大的威力和。
Input
輸入由多組數據組成。第一行為一個正整數n(n<=1000)，第二行為n個數，第i個數a[i]為第i個炸藥的威力值(0<=a[i]<=1000)。
Output
對於給定的輸入，輸出一行一個數，為所有炸彈的最大威力和。
Sample Input
6
5 9 8 2 1 6
Sample Output
77
分析：先用RMQ預處理出最大值和最小值，然後進行dp即可。dp[i]表示1到i的最大威力和。
#include
#include
#include
#include
using namespace std;
typedef __int64 LL;
const int N = 1050;
LL a[N];
LL dp[N];
LL Min[N][N], Max[N][N];
int n;
LL RMQ_Init() { // 預處理出最大值和最小值
for(int i = 1; i <= n; i++)
Min[i][0] = Max[i][0] = a[i];
for(int j = 1; (1< R) return 0;
int k = 0;
while((1<<(k+1)) <= R - L + 1) k++;
return min(Min[L][k], Min[R - (1< R) return 0;
int k = 0;
while((1<<(k+1)) <= R - L + 1) k++;
return max(Max[L][k], Max[R - (1<
