国内投资咨询网站 html模板,辽源市网站建设,企业服务有哪些,深装总建设集团股份有限公司Description Flute很喜欢柠檬。它准备了一串用树枝串起来的贝壳#xff0c;打算用一种魔法把贝壳变成柠檬。贝壳一共有\(N(1\le N\le 100000)\)只#xff0c;按顺序串在树枝上。为了方便#xff0c;我们从左到右给贝壳编号 \(1...N\) 。每只贝壳的大小不一定相同#xff0c…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\] 很可以斜率的样子欸... #includebits/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];
vectorint 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
