题解

斜率优化裸题。

有个很玄学的事情，就是我用\(f[i]=min\{f[j-1]+p[j].y*p[i].x\}\) 会很奇怪的Wa 。 明明和\(f[i]=min\{f[j]+p[j+1].y*p[i].x\}\)一模一样的呀！

如果有dalao愿意帮忙看一下就感激不尽了。

附上正确代码和错误代码

正确代码：

#include
    
     typedef long long ll;using namespace std;const int maxn = 5e4+10;const ll inf = 10000000000000LL;struct qwq{    ll x,y;    const bool operator < (const qwq rhs) const {        if(this->x==rhs.x)             return this->y
     
      x
      
       >n;    for(int i = 1;i<=n;++i)         cin>>tmp[i].x>>tmp[i].y;    sort(tmp+1,tmp+1+n);    ll mxy=0;    for(int i = n;i;--i) {        if(tmp[i].y>mxy) {            mxy=tmp[i].y;            p[++tot]=tmp[i];        }    }    reverse(p+1,p+1+tot);#ifdef force    for(int i = 1;i<=tot;++i) {        f[i]=inf;        for(int j = 0;j
       
        =slope(q[r],i)) --r;        q[++r]=i;    }#endif    cout<
        
         <
        
       
      
     
    

错误代码

#include
    
     typedef long long ll;using namespace std;const int maxn = 5e4+10;const ll inf = 10000000000000LL;double esp = 1e-6;struct qwq{    ll x,y;    const bool operator < (const qwq rhs) const {        if(this->x==rhs.x)             return this->y
     
      x
      
       >n;    for(int i = 1;i<=n;++i)         cin>>tmp[i].x>>tmp[i].y;    sort(tmp+1,tmp+1+n);    ll mxy=0;    for(int i = n;i;--i) {        if(tmp[i].y>mxy) {            mxy=tmp[i].y;            p[++tot]=tmp[i];        }    }    reverse(p+1,p+1+tot);#ifdef force    for(int i = 1;i<=tot;++i) {        f[i]=inf;        for(int j = 1;j<=i;++j) {            f[i]=min(f[i],f[j-1]+p[j].y*p[i].x);        }    }#endif#ifndef force    l=r=1;    q[1]=1;    for(int i = 1;i<=tot;++i) {        while(l
       
        <=p[i].x) ++l;        int j = q[l];        f[i]=f[j-1]+p[j].y*p[i].x;        while(l
        
         =slope(q[r],i)) --r;        q[++r]=i+1;    }#endif    cout<
         
          <