单调队列
简述
函数
维护一个单调递增的队列,队列中的元素下表保证关于
四边形不等式
简述
函数
若函数
1、当
2、当
我们称函数
一些题目
最小代价子母树
Description
设有
Solution & Code
其中
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 105;
const int inf = 1e9;
int n, w[maxn], s[maxn], f[maxn][maxn], g[maxn][maxn];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &w[i]);
for(int i = 1; i <= n; ++i) s[i] = s[i-1] + w[i];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
f[i][j] = inf;
for(int i = 1; i <= n; ++i) f[i][i] = 0, g[i][i] = i;
for(int l = 2; l <= n; ++l)
for(int i = 1, j = i + l - 1; j <= n; ++i, ++j)
for(int k = g[i][j-1]; k <= g[i+1][j] && k < j; ++k){
int tmp = f[i][k] + f[k+1][j] + s[j] - s[i-1];
if(f[i][j] > tmp){
f[i][j] = tmp;
g[i][j] = k;
}
}
printf("%d\n", f[1][n]);
return 0;
}