为了方便解释，从一个例题来说。
[例题]LuoguP1484
容易想到设\(f_{i,j,0/1}\)表示考虑到第\(i\)个坑，填了\(j\)个，当前这个坑不填/填的最大收益。
\[f_{i,j,0}=\max(f_{i-1,j,1},f_{i-1,j,0})\\
f_{i,j,1}=f_{i-1,j-1,0}+a_i
\]
复杂度为\(o(nk)\)，这个是爆炸的。我们发现对着这个式子是难以优化的，因为最多不超过\(k\)这个限制很麻烦。假如说我们没有这个限制，容易得到一个\(o(n)\)做法，这样很好。
经过打表，可以发现，若用\(g_i\)表示选择不超过\(i\)个坑种树的最大价值，在一个二维平面上刻画出\((i,g_i)\)，将形成一个上凸壳。那么，如果用一条直线去切这个凸壳，如果能刚好切到\(k\)这个位置，就可以得到答案了。
考虑二分一个斜率\(K\)，用该斜率的直线去切凸壳，什么时候刚好切到凸壳上？当然是截距最大的时候。
我们知道，截距\(b=y-kx=g(x)-Kx\)，此时因为没有\(k\)的限制，我们求一遍前\(i\)个在没有数量限制下选的最优方案，顺便记录选了多少个，容易求出最大截距\(b\)以及切到的点的横坐标\(x\)，看看这个\(x\)与\(k\)的大小关系，然后确定下一步二分的范围。因为我们维护的是最大截距，所以答案要加上\(K\times k\)。
int n, k;
ll dp[N][2], val, sum, a[N], g[N][2];void check(ll lim){val = sum = 0;dp[1][1] = a[1] - lim;g[1][1] = 1;for(int i = 2; i <= n; i++){if(dp[i - 1][0] > dp[i - 1][1]){dp[i][0] = dp[i - 1][0];g[i][0] = g[i - 1][0];} else if(dp[i - 1][0] < dp[i - 1][1]){dp[i][0] = dp[i - 1][1];g[i][0] = g[i - 1][1];} else {dp[i][0] = dp[i - 1][0];g[i][0] = min(g[i - 1][0], g[i - 1][1]);}dp[i][1] = dp[i - 1][0] + a[i] - lim;g[i][1] = g[i - 1][0] + 1;}if(dp[n][0] > dp[n][1]){val = dp[n][0], sum = g[n][0];} else if(dp[n][0] < dp[n][1]){val = dp[n][1], sum = g[n][1];} else {val = dp[n][1], sum = min(g[n][0], g[n][1]);}
}signed main(){n = read(), k = read();for(int i = 1; i <= n; i++) a[i] = readll();ll l = -1e11, r = 1e11, res = 0;check(0);if(sum <= k) return cout << val, 0;while(l <= r){int mid = (l + r) >> 1;check(mid);if(sum >= k){l = mid + 1;res = val + 1ll * mid * k;} else r = mid - 1;}for(int i = l - 5; i <= r + 5; i++){check(i);if(sum <= k){res = val + 1ll * i * k;break;}}cout << res;return 0;
}
WQS 二分的题目，常常是恰好选\(k\)个之类的，凸壳的形状打个表即可发现。二分的细节处理可能有点麻烦，于是有了上面第57到63行的 QY 牌二分。
据说本质上是降了个维。