https://ac.nowcoder.com/acm/contest/890/J
当年队友过的，斜率优化部分很水，然而据说可以wqs二分优化掉一维，回来补一补
nk的斜率优化DP没什么好说的，直接每次多一段，显然我们可以按照高度从低到高或者从高到低排序，这样肯定是最优的
这题nk可以过的，然而如果n=1e5，k=1e5的时候，就必须要wqs二分优化掉一维了，我们给每多出一段加上一个代价mid，显然这个代价越大，最后分段就越少，那么我们去找到恰好分k段的时候答案就是dp[n]-mid*k
但是wqs二分有个问题，由于是整数二分，所以不一定能恰好二分出最后分段取k段，有可能代价是mid时最少取k+1段，代价是mid+1时最少取k-1段，那么此时一定都是代价一样的
wqs二分我的还没过,下午写完，调一晚上了我吐了。。。想不通，网上只有kimoyami的题解，然而他的代码我觉得有问题，正在qq上问他还没回复
______upd:回复了，我傻逼了，我过了
由于出现上述情况时分段k-1,k,k+1的时候，代价是一样的，也就是原本的凸函数上这3点在同一条线上，本身wqs二分给每一段加一个代价就是在横坐标为段数，纵坐标为代价的坐标系的凸函数中用一条斜率为代价的线去切切点，如果出现上述情况，那么在同一条线上，算出来的答案一定是一样的，也就是说k和k + 1和k - 1，在 + mid * 横坐标后的值是一样的，虽然可能只用了k-1条边，加上了(k-1)*mid这么多多余的代价，但是要得到用了k的值，还是要减去k*mid才行
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxl=5010; int n,k;ll ans; struct rct { ll x,y; }a[maxl]; struct node { __int128 x,y,id; }s[maxl]; __int128 h[maxl],sw[maxl],sum[maxl]; __int128 dp[maxl],num[maxl]; inline bool cmp(const rct &a,const rct &b) { if(a.y==b.y) return a.x>b.x; return a.y>b.y; } inline void prework() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y); sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) { h[i]=a[i].y; sw[i]=sw[i-1]+a[i].x; sum[i]=sum[i-1]+a[i].y*a[i].x; } } inline __int128 calc(__int128 k,int id) { return s[id].y-k*s[id].x; } inline bool cmpk(node a,node b,node c) { return (__int128)(b.y-a.y)*(c.x-b.x)<=(__int128)(c.y-b.y)*(b.x-a.x); } inline bool jug(__int128 mid) { int hd=1,tl=1;node d; s[1]=node{0,0,0}; for(int i=1;i<=n;i++) { while(hd<tl && calc(h[i],hd)<calc(h[i],hd+1)) hd++; dp[i]=sum[i]-sw[i]*h[i]-calc(h[i],hd)+mid; num[i]=num[s[hd].id]+1; d=node{sw[i],sum[i]-dp[i],i}; while(hd<tl && cmpk(s[tl-1],s[tl],d)) tl--; s[++tl]=d; } return num[n]<=k; } inline void mainwork() { __int128 l=0,r=1e18,mid; while(l+1<r) { mid=(l+r)/2; if(jug(mid)) r=mid; else l=mid; } if(jug(l)) ans=dp[n]-l*k; else if(jug(l+1)) ans=dp[n]-(l+1)*k; } inline void print() { printf("%lld",ans); } int main() { prework(); mainwork(); print(); return 0; }_______________________________
下面只有O(nk)的斜率优化DP
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxl=5010; int n,m; struct node { ll x,y; }a[maxl],s[maxl]; ll h[maxl],sw[maxl],sum[maxl]; ll dp[maxl][maxl]; inline bool cmp(const node &a,const node &b) { if(a.y==b.y) return a.x>b.x; return a.y>b.y; } inline void prework() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y); sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) { h[i]=a[i].y; sw[i]=sw[i-1]+a[i].x; sum[i]=sum[i-1]+a[i].y*a[i].x; } } inline ll calc(ll k,int id) { return s[id].y-k*s[id].x; } inline bool cmpk(node a,node b,node c) { return (__int128)(b.y-a.y)*(c.x-b.x)<=(__int128)(c.y-b.y)*(b.x-a.x); } inline void mainwork() { for(int i=1;i<=n;i++) dp[1][i]=sum[i]-sw[i]*h[i]; for(int k=2;k<=m;k++) { int hd=1,tl=1;node d; s[1]=node{0,0}; for(int i=1;i<=n;i++) { while(hd<tl && calc(h[i],hd)<=calc(h[i],hd+1)) hd++; dp[k][i]=sum[i]-sw[i]*h[i]-calc(h[i],hd); d=node{sw[i],sum[i]-dp[k-1][i]}; while(hd<tl && cmpk(s[tl-1],s[tl],d)) tl--; s[++tl]=d; } } } inline void print() { printf("%lld",dp[m][n]); } int main() { prework(); mainwork(); print(); return 0; }
