你说区间DP模板题？
恭喜你，TLE快乐
看到那个数据范围了吗？
Σ(っ°Д°;)っ
没错就是1000
你知道有一个东西叫做四边形优化么？
嗯，知道了就好
刚刚放的blog里有最小值的详解，就不再赘述了
不过值得注意的是这里最大值并不满足四边形优化
?(°?°)?那怎么办
不急不急，我们看看这篇题解
看懂了么
听说这玩意还与哈夫曼树有关
每次选2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。故最终得分就是每堆果子的重量乘以它参与合并的次数。这恰好就对应一个哈夫曼树问题，把果子看做叶子节点，建树，总得分就是叶子节点的权值乘以叶子的深度之和
对于区间（i,j），不管怎么合并，叶子节点权值都一样，故要最大化其深度，显然合并（i,j-1）或（i+1,j）深度最高。
代码
1 /*************************** 2 User：Mandy 3 Language:c++ 4 Problem:stone 5 ***************************/ 6 #include<bits/stdc++.h> 7 8 using namespace std; 9 10 const int maxn = 2005; 11 12 int sum[maxn]; 13 int fa[maxn][maxn],fi[maxn][maxn]; 14 int s[maxn][maxn]; 15 16 int n; 17 18 template<class T>inline void read(T &x){ 19 x = 0;char ch = getchar();bool flag = 0; 20 while(!isdigit(ch)) flag |= ch == ‘-‘,ch = getchar(); 21 while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar(); 22 if(flag) x = -x; 23 } 24 25 void readdata(){ 26 read(n); 27 for(int i = 1;i <= n; ++ i){ 28 read(sum[i]); 29 sum[i + n] = sum[i]; 30 } 31 n <<= 1;n--; 32 for(int i = 1;i <= n; ++ i){ 33 sum[i] += sum[i - 1]; 34 s[i][i] = i; 35 } 36 } 37 38 void work(){ 39 for(int i = n;i >= 1; -- i) 40 for(int j = i+1;j <= n; ++ j){ 41 int tmp = 0x3f3f3f3f; 42 int id = 0; 43 fa[i][j] = max(fa[i][j-1],fa[i+1][j]) + sum[j] - sum[i-1]; 44 for(int k = s[i][j-1];k <= s[i+1][j];++ k){ 45 int cur = fi[i][k] + fi[k+1][j] + sum[j] - sum[i-1]; 46 if(cur < tmp){ 47 tmp = cur; 48 id = k; 49 } 50 } 51 fi[i][j] = tmp; 52 s[i][j] = id; 53 } 54 55 int ansmax = 0,ansmin = 0x3f3f3f3f; 56 n=(n+1)>>1; 57 for(int i = 1;i <= n; ++ i){ 58 ansmax = max(ansmax,fa[i][i+n-1]); 59 ansmin = min(ansmin,fi[i][i+n-1]); 60 } 61 printf("%d\n%d",ansmin,ansmax); 62 } 63 64 int main(){ 65 readdata(); 66 work(); 67 return 0; 68 }
原文：https://www.cnblogs.com/Mandy-H-Y/p/11488564.html
