Processing math: 100%

문제링크

https://www.acmicpc.net/problem/6171

 

6171번: 땅따먹기

(1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다.

www.acmicpc.net

풀이

  • 자신의 w, h 보다 모두 큰 땅이 존재하면 그 땅은 그 큰 땅에 포함하여 사면 비용을 들이지 않고 사기 가능
  • 그러한 땅들을 모두 제외하면 w 오름차순으로 정렬했을 때 h 는 내림차순으로 정렬됨
  • i 번 땅과 j 번 땅을 같이 묶어서 사면, 그 사이에 있는 땅들은 포함해도 추가 비용 들지 않음
    • i번 땅과 묶인 땅들의 비용 = w[i] * h[j] 이므로
  • 따라서, dp[i]: i 번 땅까지 사는데 필요한 최소 비용이라고 정의하면
  • dp[i]=min0≤j<i(dp[j]+w[i]∗h[j+1])
    • CHT 적용
      • x: 증가
      • 기울기: 감소
      • getMin

코드

  • 시간복잡도: O(N)
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
 
struct line {
    long long m, c;
    long long eval(long long x) {return m * x + c;}
    long long intersecX(line l) {return (c - l.c) / (l.m - m);}
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int N;
    cin >> N;
 
    vector<pair<long long, long long> > v(N);
 
    for (int i = 0; i < N; ++i) {
        cin >> v[i].first >> v[i].second;
    }
 
    sort(all(v));
 
    vector<pair<long long, long long> > v2;
 
    long long prevMax = v.back().second;
    v2.push_back(v.back());
    for (int i = N - 2; i >= 0; --i) {
        if (v[i].second > prevMax) {
            v2.push_back(v[i]);
            prevMax = v[i].second;
        }
    }
 
    reverse(all(v2));
 
    deque<line> dq;
    long long ans = 0;
    dq.push_back({v2[0].second, 0});
    for (int i = 0; i < v2.size(); ++i) {
        while (dq.size() >= 2 && dq[0].eval(v2[i].first) >= dq[1].eval(v2[i].first)) dq.pop_front();
        ans = dq.front().eval(v2[i].first);
        ans = dq.front().eval(v2[i].first);
        if (i == v2.size() - 1) break;
        line cur = {v2[i + 1].second, ans};
        while (dq.size() >= 2 && cur.intersecX(dq.back()) <= dq.back().intersecX(dq[dq.size() - 2])) dq.pop_back();
        dq.push_back(cur);
    }
 
    cout << ans << '\n';
}
728x90

'PS > BOJ' 카테고리의 다른 글

백준 2011번: 암호코드  (0) 2022.07.02
백준 13546번: 수열과 쿼리 4  (0) 2022.03.08
백준 3295번: 단방향 링크 네트워크  (0) 2022.03.07
백준 1605번: 반복 부분문자열  (0) 2022.03.07
백준 11479번: 서로 다른 부분 문자열의 개수 2  (0) 2022.03.07

문제링크

https://www.acmicpc.net/problem/13263

 

13263번: 나무 자르기

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 < a2 < ... < an, b1 > b2 > ... > bn을 만족

www.acmicpc.net

풀이

  • dp[i]: i 번 나무를 완전히 자르는데 필요한 총 충전비용의 최솟값이라 하자
  • dp[i]=max0<=j<i(dp[j]+b[j]∗a[i]) 이다.
    • 이는 컨벡스헐트릭(Convex hull trick) 을 적용할 수 있는 점화식 형태이다.
  • 또한 b[N]=0 이므로 N 번 나무를 모두 자른 이후에는 충전비용이 0이 되고 이는 곧 문제의 답이 dp[N] 임을 알 수 있다.

코드

  • 시간복잡도: O(N)
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int N;
    cin >> N;
    vector<long long> a(N), b(N);
    for (auto& e: a) {
        cin >> e;
    }
    for (auto& e: b) {
        cin >> e;
    }
 
    deque<line> dq;
    long long ans = 0;
    dq.push_front({b[0], 0});
    for (int i = 1; i < N; i++) {
        while (dq.size() >= 2 && dq[0].eval(a[i]) >= dq[1].eval(a[i]))
            dq.pop_front();
        ans = dq.front().eval(a[i]);
        line cur = {b[i], ans};
        while (dq.size() >= 2 && cur.intersectX(dq.back()) <= dq.back().intersectX(dq[dq.size() - 2]))
            dq.pop_back();
        dq.push_back(cur);
    }
    cout << ans << '\n';
}
728x90

'PS > BOJ' 카테고리의 다른 글

백준 11479번: 서로 다른 부분 문자열의 개수 2  (0) 2022.03.07
백준 3640번: 제독  (0) 2022.03.07
백준 4008번: 특공대  (0) 2022.03.06
백준 16978번: 수열과 쿼리 22  (0) 2022.03.02
백준 13548번: 수열과 쿼리 6  (0) 2022.02.28

문제링크

https://www.acmicpc.net/problem/4008

 

4008번: 특공대

입력은 세 줄로 구성된다. 첫 번째 줄에 전체 병사들 수인 양의 정수 n이 주어진다. 두 번째 줄에 특공대의 조정된 전투력 계산 등식의 계수인 세 정수 a, b, c가 주어진다. 마지막 줄에 병사들 1, 2,

www.acmicpc.net

풀이

  • dp[i]: i 번 병사들로 특공대를 만들었을 때 조정된 전체 전투력의 최댓값이라고 하고
  • v[i],pv[i] 는 각각 병사의 전투력과 그 누적합 배열이라 하자
  • dp[i] 는 i 번 병사가 속해있는 특공대가 앞의 몇명을 포함하느냐에 따라서 생각해 볼 수 있고 그를 나타낸 점화식은 다음과 같다.
    • dp[i]=max0<=j<i(dp[j]+a∗(pv[i]−pv[j])2+b∗(pv[i]−pv[j])+c)
  • 이를 정리하면 다음과 같다.
    • dp[i]=max0<=j<i(−2a∗pv[j]∗pv[i]+dp[j]+a∗pv[j]2−pv[j]+a∗pv[i]2+b∗pv[i]+c)
  • 컨벡스헐트릭(Convex hull trick)을 적용할 수 있는 점화식 형태이며 pv 배열또한 단조성을 가지고 있으므로 O(N) 에 해결할 수 있다.

코드

  • 시간복잡도: O(N)
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin >> N;
    long long a, b, c;
    cin >> a >> b >> c;
    vector<long long> v(N + 1, 0), pv(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i];
        pv[i] = v[i] + pv[i - 1];
    }
 
    deque<line> dq;
    dq.push_front({0, 0});
    long long ans = 0;
    for (int i = 1; i <= N; i++) {
        while (dq.size() >= 2 && dq[0].eval(pv[i]) <= dq[1].eval(pv[i]))
            dq.pop_front();
 
        ans = dq.front().eval(pv[i]);
 
        line cur = {-2LL * a * pv[i], a * pv[i] * pv[i] - b * pv[i] + ans +a * pv[i] * pv[i] + b * pv[i] + c };
        while (dq.size() >= 2 && cur.intersectX(dq.back()) <= dq.back().intersectX(dq[dq.size() - 2]))
            dq.pop_back();
        dq.push_back(cur);
    }
 
    cout << ans + a * pv[N] * pv[N] + b * pv[N] + c << '\n';
}
728x90

'PS > BOJ' 카테고리의 다른 글

백준 3640번: 제독  (0) 2022.03.07
백준 13263번: 나무 자르기  (0) 2022.03.06
백준 16978번: 수열과 쿼리 22  (0) 2022.03.02
백준 13548번: 수열과 쿼리 6  (0) 2022.02.28
백준 1420번: 학교 가지마!  (0) 2022.02.26

+ Recent posts

티스토리툴바