网上题解说这题naive或者显然的,我菜不看就是了

NMD不懂强行解释的,是NMB什么意思?

比如这个
还有这个

QQ截图20181108102107.png
QQ截图20181108103108.png
QQ截图20181108103057.png

你说这是找最早时间?时间你妈呢?真的傻逼。dp式子里是 $f[i]\text{ }s[i]$ 你直接用你的“二分的时间($mid$)”往dp式子里套?从$i$前面转移过来 你上界都是n?说的是判断时间,你直接拿 $s[i]$ 跟你所谓的“时间”比较?

好歹看看题解 抄完代码 再把人家写的题解也照搬一下,就成了你的博客内容?错了自己不带脑子想想?

网络垃圾!

我可去你妈的吧

二分的是s[i] 不是NMB的时间

推荐一个 链接

因为平方函数增长很快,所以对于两个位置 $i < j$,一旦 $i$ 转移到某个位置更优 那么此后 $i$ 都将比 $j$ 优

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 6;
int a[MAXN], cnt[MAXN], s[MAXN], n, m;
long long f[MAXN];
vector<int>q[MAXN];
#define mid ((l+r)>>1)
long long Get(int x, int y) {return f[x - 1] + 1ll * a[x] * y * y;}
inline int Get_s(int x, int y) {//二分出x比y优的最小的s
  int l = 1, r = n, ans = 1e9;//x永远不会比y优的话 ans = inf
  while (l <= r) {
    if (Get(x, mid - s[x] + 1) >= Get(y, mid - s[y] + 1)) ans = mid, r = mid - 1;
    else l = mid + 1;
  }
  return ans;
}


int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), s[i] = ++cnt[a[i]];
  for (int i = 1; i <= n; ++i) {
    vector<int> &v = q[a[i]];
    while (v.size() >= 2 && Get_s(*----v.end(), *--v.end()) <= Get_s(*--v.end(), i)) v.pop_back();
    //栈顶下面的元素比栈顶优的s <= 栈顶比 i 优的 s
    //当栈顶比i优的时候 第二个元素一定比栈顶优 所以栈顶没有用 可以弹出
    v.push_back(i);
    while (v.size() >= 2 && Get_s(*----v.end(), *--v.end()) <= s[i]) v.pop_back();
    //如果第二个元素比栈顶优的最小s<=s[i] 就可以弹出栈顶
    f[i] = Get(*--v.end(), s[i] - s[*--v.end()] + 1);
  }
  cout << f[n];
  return 0;
}

/*
5
2 2 1 2 3
dp[1] = 2 
dp[2] = 8
Get_s(1, 2) = 1 <= s[2](2)
s = 1的时候 1就会比2优 -> pop掉2

*/

发表评论

电子邮件地址不会被公开。 必填项已用*标注