首先我们可以打一个暴力，复杂度为\(O(n^3)\)
\(f[i]=min(f[i],f[j]+len_{max} \times wid_{max})\)
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define mk make_pair
#define pb push_back
#define pf push_front
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 5e4+5;
ll n,f[N];
inline ll read()
{
ll x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
struct ac
{
ll len,wid;
}a[N];
bool cmp(ac a,ac b)
{
return a.len<b.len;
}
int main()
{
// speed();
n=read();
for(int i=1;i<=n;i++)
{
a[i].len=read();a[i].wid=read();
// cin>>a[i].len>>a[i].wid;
}
sort(a+1,a+1+n,cmp);
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
ll le=0,w=0;
for(int k=j+1;k<=i;k++)
{
le=max(a[k].len,le);
w=max(a[k].wid,w);
}
// cout<<le<<" "<<w<<endl;
f[i]=min(f[i],f[j]+le*w);
}
}
cout<<f[n];
return 0;
}
首先,len单调递增排过序了
如何优化呢，我们可以除去一些无用的土地，即\(i>j且len_i>len_j且 wid_i>wid_j\)则\(j\)是无用的
这样我们筛选完以后，就无需找最大值最小值
\(F[i]=min(f[j]+acc[j+1].wid*acc[i].len)\)
但这样仍然过不了
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define mk make_pair
#define pb push_back
#define pf push_front
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 5e4+5;
ll n,f[N],q[N],cnt;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
struct ac
{
ll len,wid;
}a[N],acc[N];
bool cmp(ac a,ac b)
{
if(a.len==b.len)return a.wid<b.wid;
return a.len<b.len;
}
int main()
{
// speed();
n=read();
for(int i=1;i<=n;i++)
{
a[i].len=read();a[i].wid=read();
// cin>>a[i].len>>a[i].wid;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
while(cnt&&acc[cnt].wid<=a[i].wid)cnt--;
++cnt;
acc[cnt].len=a[i].len;
acc[cnt].wid=a[i].wid;
}
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<=cnt;i++)
{
// int l=1,r=1;
for(int j=0;j<i;j++)
{
//// cout<<le<<" "<<w<<endl;
f[i]=min(f[i],f[j]+acc[i].len*acc[j+1].wid);
}
// while(l<r&&)
}
// for(int i=1;i<=cnt;i++)ans=min(ans,f[i]);
cout<<f[cnt];
return 0;
}
我们可以再加上斜率优化
斜率为\(-acc[i].len\)
自变量\(acc[j+1].wid\)
因变量\(F[i]\)
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define mk make_pair
#define pb push_back
#define pf push_front
#define lid (rt<<1)
#define rid (rt<<1|1)
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 5e4+5;
ll n,f[N],q[N],cnt;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
struct ac
{
ll len,wid;
}a[N],acc[N];
bool cmp(ac a,ac b)
{
if(a.len==b.len)return a.wid<b.wid;
return a.len<b.len;
}
double X(int i)
{
return acc[i+1].wid*1.0;
}
double Y(int i)
{
return f[i]*1.0;
}
int main()
{
// speed();
n=read();
for(int i=1;i<=n;i++)
{
a[i].len=read();a[i].wid=read();
// cin>>a[i].len>>a[i].wid;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
while(cnt&&acc[cnt].wid<=a[i].wid)cnt--;
++cnt;
acc[cnt].len=a[i].len;
acc[cnt].wid=a[i].wid;
}
memset(f,0x3f,sizeof f);
f[0]=0;int l=1,r=1;
for(int i=1;i<=cnt;i++)
{
// for(int j=0;j<i;j++)
// {
// f[i]=min(f[i],f[j]+acc[i].len*acc[j+1].wid);
// }
while(l<r&&(Y(q[l+1])-Y(q[l]))<=-acc[i].len*(X(q[l+1])-X(q[l])))l++;
f[i]=f[q[l]]+acc[i].len*acc[q[l]+1].wid;
while(l<r&&(Y(q[r])-Y(q[r-1]))*(X(i)-X(q[r]))<=(Y(i)-Y(q[r]))*(X(q[r])-X(q[r-1])))r--;
q[++r]=i;
}
// for(int i=1;i<=cnt;i++)ans=min(ans,f[i]);
cout<<f[cnt];
return 0;
}