C++ 代码详解：使用单调栈和二分查找求解最小删除代价

#include<bits/stdc++.h>\nusing namespace std;\nconst int N = 2e5+10;\n#define rep(i,l,r) for(int i = l;i <= r;i++)\n#define ll long long\n\nll n,m,dp[N],h[N],cn[N]; // n: 数组长度，m: 最多删除的元素个数，dp: 动态规划数组，h: 数组h，cn: 记录删除元素的个数\nstack<ll>q1; // 单调栈\n\nstruct node{\n ll b,x;\n};\n\n// 判断以t为阈值时，最少删除元素的个数\nnode ck(ll t){\n while(!q1.empty())q1.pop();\n q1.push(1);\n rep(i,2,n){\n dp[i] = dp[i-1] + abs(h[i]-h[i-1]); // dp[i]表示前i个元素的最小删除代价（即距离之和）\n cn[i] = cn[i-1]; // cn[i]表示前i个元素的最少删除元素个数\n while(!q1.empty()){\n ll k1 = dp[q1.top()]+abs(h[q1.top()]-h[i])-t; // k1表示将第q1.top()个元素删除后，再加上当前元素与前一个元素的距离，减去阈值t的值\n \n if(k1 == dp[i])cn[i] = min(cn[i],cn[q1.top()]+1); // 如果k1等于dp[i]，则将当前元素删除，个数加1，并取个数的最小值\n if(k1 < dp[i])dp[i] = k1,cn[i] = cn[q1.top()]+1; // 如果k1小于dp[i]，则更新dp[i]和cn[i]\n \n if(h[q1.top()] >= h[i])break; // 如果栈顶元素大于等于当前元素，跳出循环\n q1.pop(); // 否则，弹出栈顶元素\n }\n q1.push(i); // 将当前元素入栈\n }\n return {dp[n],cn[n]}; // 返回最小删除代价和最少删除元素个数\n}\n\n// 二分查找最小的阈值\nvoid erfen(ll l,ll r,ll x){\n while(l < r){\n ll mid = l+(r-l+1)/2-1;\n if(ck(mid).x >= x)r = mid; // 如果以mid为阈值时，最少删除元素个数大于等于x，则说明阈值过大，更新r\n else l = mid+1; // 否则，阈值过小，更新l\n }\n cout<<r*x + ck(r).b<<'\n'; // 输出最小删除代价\n}\n\nint main(){\n ios::sync_with_stdio(0);\n cin.tie(0),cout.tie(0);\n \n cin>>n>>m;\n rep(i,1,n)cin>>h[i];\n \n if(ck(0).x <= m)cout<<ck(0).b<<'\n'; // 如果以0为阈值时，最少删除元素个数小于等于m，则输出最小删除代价\n else erfen(-1e16,1e16,m); // 否则，二分查找最小的阈值\n return 0;\n}\n