传送门 思路还不错的一道题目，难度不大，但是我在写的时候出了一些细节上的错误 显然题目中的两问都可以通过DP来解决 f[i] 表示保留旧房子 i 时，1～i最多能保留多少个旧房子 g[i] 表示 f[i] 为最优时, 1～i 的最小总花费
f[i]=max{f[j]+1}(j=0..i−1,a[i]−a[j]≥i−j)
g[i]=min{(2∗a[j]+i−j)∗(i−j−1)2+g[j]}+a[i]+b[i] ，其中 f[j] 必须是 f[i] 的最优决策点 O(n2) 的复杂度显而易见，我们来考虑优化 对于 f 的优化非常显然，分治或树状数组什么的怎样都能做，但g的转移我们还是要化简一下的 把 a[i]+b[i] 拿掉，我们把 g[i] 变成这个样子 i∗(a[j]−j)+i∗(i−1)2+(j(j+1)2−j∗a[j]−a[j]+g[j]) 这样 g[i] 就变成了一个非常传统的斜率优化DP的形式了，把 i∗(i−1)2 拿掉，每次插入一个点 (a[j]−j,j(j+1)2−j∗a[j]−a[j]+g[j]) ，转移时拿斜率为 −i 的直线去卡最小截距就可以了 理论问题解决了，那怎么实现呢 我们可以分治一发，处理左半边对右半边的影响时按照 a[i]−i 排序，拿个splay或set维护一下凸包，查询时三分就可以了 …… 可以写写试试，不过常数巨大，我们完全没必要这么做，因为观察插入点的横坐标也是 a[j]−j ，也就是说排序后插入的点也是单调的，开个vector从末尾存一下，维护下凸壳就行了 （这里我也是蠢，好久都没发现插入点是单调的，差点写了cdq套set） 最终时间复杂度 O(nlog2n) ，但要说几个容易错的地方，比如long long，比如转移要从0开始，比如f,g转移时的优先顺序等等，还有一点我没注意到，但因为数据的原因只WA了一个点，就是f在转移时要注意决策点本身必须保证有解，也就是说如果决策点不是0，那么它的 f 是必须大于0的 还有就是注意按a[i]−i排序以后 i <script type="math/tex" id="MathJax-Element-891">i</script>并不是单调的，所以不采用单调队列来维护和查询，而是vector/stack+三分 代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<vector> #define LL long long #define M 100005 #define mp make_pair using namespace std; int in() { int t=0;char ch=getchar(); while (ch>'9'||ch<'0') ch=getchar(); while (ch>='0'&&ch<='9') t=(t<<1)+(t<<3)+ch-48,ch=getchar(); return t; } int n; int a[M],b[M],f[M],id[M]; LL g[M]; typedef pair<int,LL>node; vector<node> v; bool cmp(int x,int y) { if (a[x]-x==a[y]-y) return x<y; return a[x]-x<a[y]-y; } node operator -(node a,node b){return mp(a.first-b.first,a.second-b.second);} LL operator *(node a,node b){return a.first*b.second-a.second*b.first;} void solve(int l,int r) { if (l==r) return; int mid=l+r>>1,cnt=0; solve(l,mid); for (int i=l;i<=r;++i) id[++cnt]=i; sort(id+1,id+cnt+1,cmp); node now; int mx=-1,L,R,mid1,mid2; for (int i=1;i<=cnt;++i) if (id[i]<=mid) { if (f[id[i]]<mx) continue; if (id[i]!=0&&!f[id[i]]) continue; if (f[id[i]]>mx) v.clear(), mx=f[id[i]]; now=mp(2*a[id[i]]-2*id[i],1LL*id[i]*(id[i]+1)-1LL*2*id[i]*a[id[i]]-2*a[id[i]]+2*g[id[i]]); while (v.size()>1&&(v[v.size()-1]-v[v.size()-2])*(now-v[v.size()-1])<=0) v.pop_back(); v.push_back(now); } else { if (f[id[i]]>mx+1) continue; if (f[id[i]]<mx+1) g[id[i]]=1e18; f[id[i]]=mx+1; L=0,R=v.size()-1; for (;R-L>2;) { mid1=(R-L)/3+L; mid2=(R-L)/3*2+L; if (1LL*v[mid1].first*id[i]+v[mid1].second>1LL*v[mid2].first*id[i]+v[mid2].second) L=mid1+1; else R=mid2-1; } for (int j=L;j<=R;++j) g[id[i]]=min(g[id[i]],(1LL*v[j].first*id[i]+1LL*id[i]*(id[i]-1)+v[j].second)/2+a[id[i]]+b[id[i]]); } solve(mid+1,r); } main() { n=in(); for (int i=1;i<=n;++i) a[i]=in(); for (int i=1;i<=n;++i) b[i]=in(); for (int i=1;i<=n;++i) g[i]=1e18; solve(0,n); int maxn=0; LL ans; for (int i=1;i<=n;++i) { g[i]+=1LL*(n-i)*(a[i]+1)+1LL*(n-i)*(n-i-1)/2; if (maxn<f[i]) maxn=f[i],ans=g[i]; else if (maxn==f[i]) ans=min(ans,g[i]); } printf("%d %lld\n",maxn,ans); }