qqs2점 중 2점 조건 세부적 사고

먼저 예를 들어 복습하고 정수 수조 a[]를 정하고 수조를 k부로 나누어 k자단의 제곱과 합의 최대치를 구한다(즉min⁡ {∑i = 1 k s u m i 2}\min\{\sum^ {k} {i = 1} {sum i^2}\} min {∑i=1k sumi2}).
전이 방정식은 dp [i] [j] = m a x {d p [x] [j-3] + w(x+1,i)} dp[i] [j] = max\{dp[x] [j-1] + w(x+1,i)\dp[i] [j]=max{dp[x] [j-3] + w(x+1,i)}, dp [n] dp[n][k]dp[n][k]]를 요구한다.2D1D 동적 계획 시간의 복잡도는 O(n3)O(n^3)O(n3)로 최적화가 필요하다.f[k]=dp[n][k]f[k]=dp[n][k]=dp[k]=dp[n][k], fff는 볼록함수로 (k, f[k])(k, f[k])(k, f[k])와 서로 접하는 직선을 구성하면 f[k]f[k] f[k]f[k]]를 구할 수 있다. 이 직선의 경사율을 2분하면 복잡도를 O(log⁡n)O(logn} {logn})로 낮출 수 있다.이 문제와 결합하여 더욱 형상적으로 말하면 k가 클수록 최대치가 커지기 어려워지고 튀어나온다.우리는 두 가지 대가로 v a l val val을 나눈다. 매번 정답을 나누면 d p [i] = m a x {d p [x] + w (x + 1,i) - v a l} dp[i] = max\{dp[x] + w (x + 1,i) - val\} dp[i] = max {dp [x] + w (x + 1,i) - val\= max {dp [x] + w (x + 1,i) - val} 를 빼면 최대치를 나누면 할수록 성장하기 어렵다는 뜻이다.v a l val val이 너무 크면 f f f가 k k k가 비교적 작은 곳에서 가장 큰 값을 얻는다.반대로 해도 마찬가지다.적절한 v a l val val의 경우 제목에 지정된 kk의 값을 입력하여 가장 높은 값을 얻을 수 있습니다. 이때'절선'을 찾을 수 있습니다.

struct DP { int f, k; } dp[N];

bool operator < (DP a, DP b) {
    if (a.f != b.f) return a.f < b.f;
    return a.k < b.k;
}
    
inline DP solve (int val) {
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			dp[i] = max(dp[i], { dp[j].f + w(j + 1, i) - val, dp[j].k + 1 });
        }
    }
    return dp[n];
}

int wqs (void) {
	int st, en, md;
    while (st != en) {
		int md = (st + en + 1) >> 1;
        if (solve(md).k > k) st = md;
        else en = md - 1;
    }
    return solve(st).f;
}

주의해야 할 것은 함수가 엄격하게 튀어나오지 않을 수도 있고, 절선이 여러 점을 동시에 통과할 수도 있다는 것이다.이 예제에서 설명하자면 어떤 v a l val val에 대해 여러 개의 kk가 dp[n]dp[n]dp[n]를 최대치로 하고 2분 동안 우리는 문제를 kk로 배제할 수 없도록 주의해야 한다.다시 불러오는 것이 기호보다 작다는 것을 보면 우리가 최종적으로 되돌아온 dp[n]를 알 수 있다.k dp[n].k dp[n].k는 조건을 만족시키는 가장 큰 kk라는 점을 고려해야 한다.그럼 재부팅할 때 거꾸로 쓰면?다음과 같습니다.

bool operator < (DP a, DP b) {
	if (a.f != b.f) return a.f < b.f;
    return a.k > b.k;
}

int wqs (void) {
    ...
        int md = (st + en) >> 1;
        if (solve(md).k > k) st = md + 1;
        else en = md;
    ...
}

어쨌든 디버그를 할 때는 이 점을 생각해야 한다. 하지만 내가 이런 문제를 칠 차례는 아니다.