Description

Flute很喜歡檸檬。它準備了一串用樹枝串起來的貝殼，打算用一種魔法把貝殼變成檸檬。貝殼一共有\(N(1\le N\le 100000)\)只，按順序串在樹枝上。為了方便，我們從左到右給貝殼編號 \(1...N\) 。每只貝殼的大小不一定相同，貝殼 \(i\) 的大小為 \(s_i(1 \le s_i \le10000)\) 。變檸檬的魔法要求，Flute每次從樹枝一端取下一小段連續的貝殼，并選擇一種貝殼的大小 \(s_0\) 。如果 這一小段貝殼中 大小為 \(s_0\) 的貝殼有 \(t\) 只，那么魔法可以把這一小段貝殼變成 \(s_0t^2\) 只檸檬。Flute可以取任意多次貝殼，直到樹枝上的貝殼被全部取完。各個小段中，Flute選擇的貝殼大小 \(s_0\) 可以不同。而最終 Flute 得到的檸檬數，就是所有小段檸檬數的總和。Flute 想知道，它最多能用這一串貝殼變出多少檸檬。請你幫忙解決這個問題。

Input

第 \(1\) 行：一個整數，表示 \(N\)。
第 \(2 ... N + 1\) 行：每行一個整數，第 \(i + 1\) 行表示 \(s_i\) 。

Output

僅一個整數，表示 Flute 最多能得到的檸檬數。

Sample Input

5
2
2
5
2
3

Sample Output

21

Solution

考慮DP， \(f[i]\) 表示前 \(i\) 個的最大價值。

發現每一段的開頭結尾應該是同一個顏色才會最優，否則不如單出來選。

對于 \(f[i]\)，假設之前存在一個點 \(j\)，這個點的顏色 \(a[j]\) 與 \(i\) 的顏色 \(a[i]\) 相等，那么我們可以讓 \(f[i]\) 由 \(j\) 轉移， \(s[i]\) 代表前 \(i\) 個數里 \(a[i]\) 出現的次數，價值為 \[f[j-1]+a[j]\times (s[i]-s[j]+1)^2\]

很可以斜率的樣子欸...

#include<bits/stdc++.h> using namespace std;#define N 100001 #define rep(i, a, b) for (int i = a; i <= b; i++) #define ll long longinline int read() {int x = 0, flag = 1; char ch = getchar(); while (!isdigit(ch)) { if (!(ch ^ '-')) flag = -1; ch = getchar(); }while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); return x * flag; }int n; ll a[N], f[N]; int cnt[N], s[N]; vector<int> q[N];inline ll calc(int x, int y) { return f[x - 1] + a[x] * y * y; } inline int k(int x, int y) {int l = 1, r = n, mid, ret = n + 1;while(l <= r) if(calc(x, (mid = l + r >> 1) - s[x] + 1) >= calc(y, mid - s[y] + 1)) ret = mid, r = mid - 1; else l = mid + 1;return ret; }int main() {n = read();rep(i, 1, n) {int t = a[i] = read(); cnt[t]++, s[i] = cnt[t];while(q[t].size() >= 2 && k(q[t][q[t].size() - 2], q[t][q[t].size() - 1]) <= k(q[t][q[t].size() - 1], i)) q[t].pop_back();q[t].push_back(i);while(q[t].size() >= 2 && k(q[t][q[t].size() - 2], q[t][q[t].size() - 1]) <= s[i]) q[t].pop_back();f[i] = calc(q[t][q[t].size()-1], s[i] - s[q[t][q[t].size()-1]] + 1);}cout << f[n];return 0; }

轉載于:https://www.cnblogs.com/aziint/p/8419030.html

總結

以上是生活随笔為你收集整理的bzoj4709 [Jsoi2011]柠檬的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。