还没有学会斜率优化...可以直接单调栈，参考neither_nor的博客，在代码里面写了一点注释：
1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 #define ll long long 5 using namespace std; 6 7 int n, s, cnt[10005], pre[100005], color[100005]; 8 vector < int > stk[10005]; 9 ll f[100005]; 10 11 ll count ( int x, int num ) { 12 return f[x-1] + (ll)color[x] * num * num; 13 } 14 15 int find ( int x, int y ) {//x，y是需要判断的下标，find的是x超过y的位置 16 int l = 1, r = n, res = n + 1; 17 while ( l <= r ) { 18 int mid = ( l + r ) >> 1; 19 if ( count ( x, mid - pre[x] + 1 ) >= count ( y, mid - pre[y] + 1 ) ) {//mid查找的是当前颜色的第几个入栈时间 20 res = mid; r = mid - 1; 21 } else l = mid + 1; 22 } 23 return res; 24 } 25 26 int main ( ) { 27 scanf ( "%d", &n ); 28 for ( int i = 1; i <= n; i ++ ) { 29 scanf ( "%d", &s ); 30 cnt[s] ++; 31 color[i] = s; 32 pre[i] = cnt[s]; 33 while ( stk[s].size ( ) >= 2 && find ( stk[s][stk[s].size ( ) - 2], stk[s][stk[s].size ( ) - 1] ) <= 34 find ( stk[s][stk[s].size ( ) - 1], i ) ) stk[s].pop_back ( );//防止第二个元素超过栈顶的时间比栈顶超过i的时间早，此时栈顶没用 35 stk[s].push_back ( i );//先推入防止最后从0更新 36 while ( stk[s].size ( ) >= 2 && find ( stk[s][stk[s].size ( ) - 2], stk[s][stk[s].size ( ) - 1] ) <= 37 pre[i] ) stk[s].pop_back ( );//i是这种颜色第pre[i]个入栈的 //第二个元素超过栈顶的时间比第一个元素进入的时间早，栈顶就没用了 38 f[i] = count ( stk[s][stk[s].size ( ) - 1], pre[i] - pre[stk[s][stk[s].size ( ) - 1]] + 1 ); 39 } 40 ll ans = 0; 41 for ( int i = 1; i <= n; i ++ ) 42 ans = max ( ans, f[i] ); 43 printf ( "%lld\n", ans ); 44 return 0; 45 }
原文：https://www.cnblogs.com/wans-caesar-02111007/p/9477413.html