1 条题解
-
0
注意到若一个长方形的长、宽同时小于等于另一个长方形,那么可以忽略这个长方形。此时可以得到一个长递增、宽递减的长方形序列,易知把序列分割成若干连续段是最优的。
设到第 个长方形为止的最小费用为 ,则 $dp(i)=\min\limits_{0\leq j < i}\left[dp(j)+l_{j+1}\cdot w_i\right]$。
斜率优化解决即可。时间复杂度 。
/** * @date: 2024.04.06 * @problem: P2900, SPACQUIRE * @tags: 动态规划, 斜率优化 */ #include<bits/stdc++.h> using namespace std; int n,w[50001],l[50001]; pair<int,int> rec[50001]; long long x[50001],y[50001],dp[50001]; int q[50001],head,tail; inline double slope(int u,int v){ return (y[v]-y[u])*1.0/(x[v]-x[u]); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&rec[i].first,&rec[i].second); { sort(rec+1,rec+1+n,[&](pair<int,int> x,pair<int,int> y){return x>y;}); int m=0; for(int i=1;i<=n;i++) if(rec[i].second>l[m])w[++m]=rec[i].first,l[m]=rec[i].second; n=m; reverse(w+1,w+1+n); reverse(l+1,l+1+n); } x[0]=-l[1]; for(int i=1;i<=n;i++){ while(head<tail&&slope(q[head],q[head+1])<=w[i])head++; dp[i]=dp[q[head]]+1ll*w[i]*l[q[head]+1]; x[i]=-l[i+1],y[i]=dp[i]; while(head<tail&&slope(q[tail],i)<slope(q[tail-1],q[tail]))tail--; q[++tail]=i; } printf("%lld\n",dp[n]); return 0; }
- 1
信息
- ID
- 2600
- 时间
- 1000ms
- 内存
- 1536MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者