[APIO/CTSC2007] 데이터 백업 문제 해결

전송문
우선 수조를 차분시키면 차분수 그룹에서 kk개의 서로 인접하지 않는 수를 찾아 그것들의 수를 최소화해야 한다.
먼저 폭력적인 DP 방법이 하나 있다. f(i, j, 0/1) f(i, j, 0/1) f(i, j, 0/1)는 앞의 i i i 개수를 표시하고 j j 개, 첫 번째 i i 개수는 선택하지 않거나 선택하지 않으며 가장 작은 것이 얼마인지를 나타낸다.f ( i , j , 0 ) = min ⁡ ( f ( i − 1 , j , 0 ) , f ( i − 1 , j , 1 ) ) , f ( i , j , 1 ) = f ( i − 1 , j − 1 , 0 ) + d i f(i,j,0)=\min(f(i-1,j,0),f(i-1,j,1)),f(i,j,1)=f(i-1,j-1,0)+d_f(i,j,0)=min(f(i-3-1,j,0),f(i-3-1,j,1),f(i,j,1)=f(i,j,1)=f(i-3-1,j-1,0)+di 이런 이동은 말할 필요가 없다.
그러나 이런 복잡도는 O(nk)O(nk)O(nk)로 넘을 수 없다.해결 방법은 방법에 따라 wqs 2점 최적화를 써서 jjj의 1차원을 낮추면 된다.

#include 
#include 
#include 
#include 

template <typename T> inline void read(T& x) {
    int f = 0, c = getchar(); x = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
    if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
    read(x); read(args...); 
}
template <typename T> void write(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }

typedef long long LL;
const int maxn = 1e5 + 207;
const LL inf = 1e10;
int n, K;
LL d[maxn];
// f[i][0] = min(f[i-1][0], f[i-1][1])
// f[i][1] = f[i-1][0] + d[i] - mid

struct Data {
    int cnt;
    LL f;
    Data() : cnt(0), f(0) {}
    Data(int a, LL b) : cnt(a), f(b) {}
};
Data dp[maxn][2];
inline bool operator<(const Data &lhs, const Data &rhs) {
    return lhs.f < rhs.f || (lhs.f == rhs.f && lhs.cnt < rhs.cnt);
}

inline void solve(LL mid) {
    for (int i = 0; i <= n; ++i)
        dp[i][0] = dp[i][1] = Data();
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = std::min(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = Data(dp[i - 1][0].cnt + 1, dp[i - 1][0].f + d[i] - mid);
    }
}

int main() {
    read(n, K);
    for (int i = 0; i < n; ++i) read(d[i]);
    for (int i = n - 1; i; --i) d[i] -= d[i - 1];
    d[0] = 0; --n;
    LL left = 0, right = inf, ans;
    while (left <= right) {
        LL mid = (left + right) >> 1;
        solve(mid);
        const Data &mn = std::min(dp[n][0], dp[n][1]);
        if (mn.cnt <= K)
            ans = mn.f + mid * K, left = mid + 1;
        else right = mid - 1;
    }
    writeln(ans);
    return 0;
}