您的位置: 首页  >  IT文章  >  玩具装箱&土地购买

玩具装箱&土地购买

分类: IT文章 • 2023-03-24 19:31:37

　　今天一天8h 写了两道斜率优化的题（别问我效率为什么这么低 代码bug太多了）

关键是思考的不周全 估计是写的题少手生 以后就会熟练起来了吧。

玩具装箱&土地购买

这道题显然有一个n^2的dp方程 

设f[i]表示前i件物品放好的最小费用   f[i]=min(f[i],f[j]+((i-j-1)*(Ci-Cj)-L)^2);

那么这样我们可以愉快的得到了30分但我的常数比较大 是20分。

针对上述式子我们可以将其变形 把和i相关的都放到一边 因为此时和i相关的除了f[i]都是定值

//对上述式子进行变形 可得：

//f[j]+(k-j-C[j])*(k-j-C[j]);f[j]+(k-(j+c[j]))*(k-(j+C[j]))

//f[i]=min(f[i],f[j]+(k-j-C[j])*(k-j-C[j]));

//设 x=j+C[j]; //f[i]=min(f[i],f[j]+(k-x)*(k-x));

//f[i]=min{f[j]+k^2-2KX+X^2}

//f[j]=f[i]-K^2+2KX-X^2;

//f[j]=f[i]-X^2+2KX-K^2;

//f[j]+X^2+K^2=f[i]+2KX;

//以 K为斜率 2X为横坐标那么f[i]为截距

//截距越小越好 所以采用单调队列这里 没有任何不合法K

//发现斜率应该是单调递增有可能不严格单调递增但是我们仍可以维护下凸壳

//此时 f[i]=f[q[h]]+X^2-2KX+K^2;

然后 双端队列维护一下注意一下细节即可得出答案 亲测不会爆long long

关键是代码别打错什么+1 -1少了的问题也可能只有我这个NC 才会打出来。

//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<utility>
#include<queue>
#include<deque>
#include<vector>
#include<stack>
#include<algorithm>
#include<set>
#include<bitset>
#include<map>
#define INF 2147483646
using namespace std;
char buf[1<<15],*ft,*fs;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline long long read()
{
    long long x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
inline void put(long long x)
{
    x<0?x=-x,putchar('-'):0;
    long long num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar(10);return;
}
//针对这道HNOI 2008
//考虑dp
//设f[i]表示前i件物品放好的最小费用
//f[i]=min(f[i],f[j]+((i-j-1)*(Ci-Cj)-L)^2);
const long long MAXN=50002;
long long n,L;
long long f[MAXN],C[MAXN];
long long q[MAXN],l,r;
long long y(long long x)
{
    return q[x]+C[q[x]];
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();L=read();
    for(long long i=1;i<=n;i++)
    {
        C[i]=read();
        C[i]+=C[i-1];
    }
    for(long long i=1;i<=n;i++)f[i]=INF;
    f[0]=0;q[++r]=0;l=r;
    for(long long i=1;i<=n;i++)
    {
        long long k=i-1+C[i]-L;
        while(l<r&&(f[q[l+1]]-f[q[l]]+y(l+1)*y(l+1)-y(l)*y(l)<=2*k*(y(l+1)-y(l))))l++;
        long long x=y(l);
        //f[i]=min(f[i],f[j]+((i-j-1)+(C[i]-C[j])-l)*((i-j-1)+(C[i]-C[j])-L));
        //设k = i-1+C[i]-l
        //对上述式子进行变形 可得：
        //f[j]+(k-j-C[j])*(k-j-C[j]);f[j]+(k-(j+c[j]))*(k-(j+C[j]))
        //f[i]=min(f[i],f[j]+(k-j-C[j])*(k-j-C[j]));
        //设 x=j+C[j];
        //f[i]=min(f[i],f[j]+(k-x)*(k-x));
        //f[i]=min{f[j]+k^2-2KX+X^2}
        //f[j]=f[i]-K^2+2KX-X^2;
        //f[j]=f[i]-X^2+2KX-K^2;
        //f[j]+X^2+K^2=f[i]+2KX;
        //以 K为斜率 2X为横坐标那么f[i]为截距
        //截距越小越好 所以采用单调队列这里 没有任何不合法K
        //发现斜率应该是单调递增有可能不严格单调递增但是我们仍可以维护下凸壳
        //此时 f[i]=f[q[h]]+X^2-2KX+K^2;
        f[i]=f[q[l]]+k*k-2*k*x+x*x;
        while(l<r&&(((f[q[r]]-f[q[r-1]]+y(r)*y(r)-y(r-1)*y(r-1))*2*(i+C[i]-q[r]-C[q[r]]))>=(((f[i]-f[q[r]]+(i+C[i])*(i+C[i])-y(r)*y(r))*2*(y(r)-y(r-1))))))r--;
        q[++r]=i;
    }
    put(f[n]);
    return 0;
}
View Code

玩具装箱&土地购买

这道题就比较有意思了 n^3 方的dp直接写啊

//f[i]表示前i个田地购买后的最小花费  f[i]=min(f[i],f[j]+ymax(j+1~i)*x[i]);

机智的我知道 搞一个单调队列优化似乎可以得到n^2优秀复杂度

for(int i=1;i<=n;i++)
    {
        l=r=0;
        for(int k=1;k<=i;k++)
        {
            while(l<r&&t[q[r]].y<=t[k].y)r--;
            q[++r]=k;
        }
        //cout<<r<<endl;
        for(int j=0;j<i;j++)
        {
            while(l<r&&q[l]<=j)l++;
            f[i]=min(f[i],f[j]+(ll)t[q[l]].y*t[i].x);
        }
    }
    put(f[n]);
View Code

这样可以愉快的得到60分 可是这让我非常的郁闷 因为这远远的偏离了正解

采用玩具装箱的斜率优化公式如果没有想到去重去掉不必要的土地的话 根本是不可能采用玩具装箱的优化方式的。

那么 只好看了一眼ppt 学长用另外一种方法进行了斜率优化。

设 对于i的某个状态 如果 u<v 且 V(u)>V(v)

那么 f[u-1]+x[i]*y[u]>f[v-1]+x[i]*y[v]

f[u-1]-f[v-1]>x[i]*(y[v]-y[u])

(f[u-1]-f[v-1])/(y[v]-y[u])>x[i]

因为 x[i]不断递增所以当出现这种情况时v点一定比u点更优

从这个角度优化 打完后发现细节出现了点问题因为无法保证当前高度是最高的

考虑去重或者去掉不必要的田地这样维护一个单调的栈即可。

然后数出所有可执行的田地那么横坐标与纵坐标都具有单调性了。

愉快的进行斜率优化。。。如果用玩具装箱的斜率优化方式的话需要直接想到先去重判断掉不必要的状态

然后对此时的dp式子进行改变 这样也是可以的。

所以说两种方法其实是殊途同归了非常的巧妙！

值得一提的是可以开多个函数使自己冗杂的程序变得简明 或者交叉乘的时候换成double 再除法 这样可以避免一些问题如爆longlong

最后细节真的很重要这道题我调了6h 才调出来，好在对斜率优化的感触非常深！

//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<utility>
#include<queue>
#include<deque>
#include<vector>
#include<stack>
#include<algorithm>
#include<set>
#include<bitset>
#include<map>
#define INF 2147483646
#define ll long long
using namespace std;
char buf[1<<15],*ft,*fs;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline long long read()
{
    long long x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
inline void put(long long x)
{
    x<0?x=-x,putchar('-'):0;
    long long num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar(10);return;
}
const ll MAXN=50002;
struct wy
{
    ll x,y;
    friend ll operator < (const wy x,const wy y)
    {
        if(x.x==y.x)return x.y<y.y;
        return x.x<y.x;
    }
}t[MAXN];
ll min(ll x,ll y){return x>y?y:x;}
ll n;
ll x[MAXN],y[MAXN],f[MAXN];
//f[i]表示前i个田地购买后的最小花费
//f[i]=min(f[i],f[j]+ymax(j+1~i)*x[i]);
//暴力求解n^3 貌似 可以单调队列稍稍优化一下 n^2
//n<=50000 还是过不了再次优化看到dp式子发现没有任何单调性可言
//优化不了了肿么办 考虑状态之间的关系 
//设 对于i的某个状态 如果 u<v 且 V(u)>V(v)
//那么 f[u-1]+x[i]*y[u]>f[v-1]+x[i]*y[v]
//f[u-1]-f[v-1]>x[i]*(y[v]-y[u])
//(f[u-1]-f[v-1])/(y[v]-y[u])>x[i]
//因为 x[i]不断递增所以当出现这种情况时v点一定比u点更优
//从这个角度优化 打完后发现细节出现了点问题因为无法保证当前高度是最高的 
//考虑去重或者去掉不必要的田地
ll q[MAXN],l=1,r,s[MAXN],h;
inline void discrete()
{
    for(long long i=1;i<=n;i++)
    {
        while(h&&t[s[h]].y<=t[i].y)h--;
        s[++h]=i;
    }
    return;
}
double k(long long p,long long q)
{
    return ((1.0*(f[p-1]-f[q-1]))/(1.0*(y[p]-y[q])));
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();
    for(ll i=1;i<=n;i++)t[i].x=read(),t[i].y=read();
    sort(t+1,t+1+n);
    discrete();
    for(int i=1;i<=h;i++)f[i]=INF*1000000ll;
    //put(h);
    //for(long long i=1;i<=n;i++)cout<<t[i].x<<' '<<t[i].y<<endl;
    for(ll i=1;i<=h;i++)x[i]=t[s[i]].x,y[i]=t[s[i]].y;
    f[1]=x[1]*y[1];
    q[++r]=1;    
    for(long long i=2;i<=h;i++)
    {
        while(l<r&&((f[q[l]-1]+x[i]*y[q[l]])>=(x[i]*y[q[l+1]]+f[q[l+1]-1])))l++;
        f[i]=min(f[i],f[i-1]+y[i]*x[i]);
        f[i]=min(f[i],f[q[l]-1]+y[q[l]]*x[i]);
        while(l<r&&(k(q[r-1],q[r])<k(q[r],i)))--r;
        q[++r]=i;
    }
    put(f[h]);
    return 0;
}
View Code

用了另一种方法重写了一遍真的是殊途同归 经典优化。这次我只花了20min（个人感觉第一种更舒服一点）

//去掉没有价值的东西之后发现dp式子变成了
//f[i]=min(f[i],f[j-1]+y[j]*x[i]);
//又再次成为了可以斜率优化的式子 虽然上述方法也是可以的
//f[i]=f[j-1]+y[j]*x[i]; f[j-1]=f[i]-y[j]*x[i];
//这样的话x[i]为单调递增的斜率 -y[j]为 横坐标 f[j-1]为纵坐标
//使截距f[i]最小即可 那么此时我要让 -y[j]*x[i]越小越好
//换个说法因为-y[j]为负 那么我需要让y[j]*x[i]越大越好
//怎么说都和以前的不太一样因为这个地方竟然有个负号
//看了几张图之后发现和原来的近乎一样 维护一下就好了

对于点在负半轴上我只需要 还是维护两点斜率比当前斜率大的部分即可。

还是维护一个下凸壳没了。

//#include<bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<utility>
#include<queue>
#include<deque>
#include<vector>
#include<stack>
#include<algorithm>
#include<set>
#include<bitset>
#include<map>
#define INF 2147483646
#define ll long long
using namespace std;
char buf[1<<15],*ft,*fs;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline long long read()
{
    long long x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
inline void put(long long x)
{
    x<0?x=-x,putchar('-'):0;
    long long num=0;char ch[50];
    while(x)ch[++num]=x%10+'0',x/=10;
    num==0?putchar('0'):0;
    while(num)putchar(ch[num--]);
    putchar(10);return;
}
const ll MAXN=50002;
struct wy
{
    ll x,y;
    friend ll operator < (const wy x,const wy y)
    {
        if(x.x==y.x)return x.y<y.y;
        return x.x<y.x;
    }
}t[MAXN];
ll min(ll x,ll y){return x>y?y:x;}
ll n;
ll x[MAXN],y[MAXN],f[MAXN];
//f[i]表示前i个田地购买后的最小花费
//f[i]=min(f[i],f[j]+ymax(j+1~i)*x[i]);
//暴力求解n^3 貌似 可以单调队列稍稍优化一下 n^2
//n<=50000 还是过不了再次优化看到dp式子发现没有任何单调性可言
//优化不了了肿么办 考虑状态之间的关系 
//设 对于i的某个状态 如果 u<v 且 V(u)>V(v)
//那么 f[u-1]+x[i]*y[u]>f[v-1]+x[i]*y[v]
//f[u-1]-f[v-1]>x[i]*(y[v]-y[u])
//(f[u-1]-f[v-1])/(y[v]-y[u])>x[i]
//因为 x[i]不断递增所以当出现这种情况时v点一定比u点更优
//从这个角度优化 打完后发现细节出现了点问题因为无法保证当前高度是最高的 
//考虑去重或者去掉不必要的田地
//去掉没有价值的东西之后发现dp式子变成了 
//f[i]=min(f[i],f[j-1]+y[j]*x[i]);
//又再次成为了可以斜率优化的式子 虽然上述方法也是可以的
//f[i]=f[j-1]+y[j]*x[i]; f[j-1]=f[i]-y[j]*x[i];
//这样的话x[i]为单调递增的斜率 -y[j]为 横坐标 f[j-1]为纵坐标
//使截距f[i]最小即可 那么此时我要让 -y[j]*x[i]越小越好
//换个说法因为-y[j]为负 那么我需要让y[j]*x[i]越大越好
//怎么说都和以前的不太一样因为这个地方竟然有个负号 
//看了几张图之后发现和原来的近乎一样 维护一下就好了
ll q[MAXN],l=1,r,s[MAXN],h;
inline void discrete()
{
    for(long long i=1;i<=n;i++)
    {
        while(h&&t[s[h]].y<=t[i].y)h--;
        s[++h]=i;
    }
    return;
}
double k(long long u,long long v)
{
    return ((f[u-1]-f[v-1])*1.0)/(1.0*(-y[u]+y[v]));
}
int main()
{
    //freopen("1.in","r",stdin);
    n=read();
    for(ll i=1;i<=n;i++)t[i].x=read(),t[i].y=read();
    sort(t+1,t+1+n);
    discrete();
    for(long long i=1;i<=h;i++)f[i]=INF*1000000ll;
    //put(h);
    //for(long long i=1;i<=n;i++)cout<<t[i].x<<' '<<t[i].y<<endl;
    for(ll i=1;i<=h;i++)x[i]=t[s[i]].x,y[i]=t[s[i]].y;
    f[1]=x[1]*y[1];
    q[++r]=1;
    for(long long i=2;i<=h;i++)
    {
        while(l<r&&k(q[l+1],q[l])<x[i])++l;
        f[i]=min(x[i]*y[i]+f[i-1],f[q[l]-1]+y[q[l]]*x[i]);
        while(l<r&&k(q[r-1],q[r])>k(q[r],i))--r;
        q[++r]=i;
    }
    put(f[h]);
    return 0;
}
View Code

对于这两道题总结一下犯错误的地方 ：

1 细节打错的比较多稍加一对括号什么的 多打-1少打+1的地方需注意 不能很马虎。要严谨。

2 双端队列进入的时候需要先把队尾的比较出来再加进去 例如上一题的状态的缺漏之处 我理所当然的写错了。

3 分析斜率优化时对于点的分布 的问题一定仔细分析怎么搞才是最优的

4 对于一些计算斜率的尽量使用函数来简化自己的程序 不要太过冗杂 

不可能这三个字，你说的太多了

相关推荐