4709: [Jsoi2011]柠檬

https://www.lydsy.com/JudgeOnline/problem.php?id=4709

分析：

　　决策单调性+栈+二分。

　　首先挖掘性质：每个段选的数必须是起点或者终点，起点和终点的数必须是一样的。否则可以去掉起点或者终点的一个数，答案不会变差。

　　然后又n^2dp：f[i]=f[j]+cost(j,i)，cost(j,i)=a[i]*(s[i]-s[j])^2。s[i]表示到i时候，a[i]的个数。

　　单独对每个数字考虑，因为后面存在一个平方，那么越大，增长的越快。所有下一个位置转移的位置只能比上一个位置靠前（决策单调性！），然后维护一个队列，每次从队尾转移（实际上是一个栈）。如果队尾的元素不如队尾的下一个优，弹出队尾。

　　可能存在队尾的元素，小于队尾-1的，但是队尾-2却更优。就是队尾-2的元素，可以覆盖它们的区间，于是加入一个点的时候，求出转移最远转移到的位置，判断。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<map>
11 #define fi(s) freopen(s,"r",stdin);
12 #define fo(s) freopen(s,"w",stdout);
13 #define top ((int)(sk[x].size()) - 1)
14 using namespace std;
15 typedef long long LL;
16 
17 inline int read() {
18     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
19     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
20 }
21 
22 const int N = 100005;
23 LL f[N];
24 int s[N], a[N], cnt[N];
25 vector<int> sk[N];
26 int n;
27 
28 LL Calc(int x,int y) {
29     return f[x - 1] + 1ll * a[x] * y * y;
30 }
31 
32 int find(int x,int y) {
33     int l = 1, r = n, ans = n + 1;
34     while (l <= r) {
35         int mid = (l + r) >> 1;
36         if (Calc(x, mid - s[x] + 1) >= Calc(y, mid - s[y] + 1)) ans = mid, r = mid - 1;
37         else l = mid + 1;
38     }
39     return ans;
40 }
41 
42 int main() {
43     n = read();
44     for (int i=1; i<=n; ++i) {
45         int x = read();
46         a[i] = x;
47         s[i] = ++cnt[x];
48         while (top >= 1 && find(sk[x][top - 1], sk[x][top]) <= find(sk[x][top], i)) sk[x].pop_back();
49         sk[x].push_back(i);
50         while (top >= 1 && find(sk[x][top - 1], sk[x][top]) <= s[i]) sk[x].pop_back();
51         f[i] = Calc(sk[x][top], s[i] - s[sk[x][top]] + 1);
52     }
53     cout << f[n];
54     return 0;
55 }