hckim

문제링크

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

풀이

$dp[i][r][c]$ 를 만들고자 하는 문자열 target의 i 번째 문자 위치 부터 끝까지 만드려고 할 때 (r, c) 위치부터 출발했을 때 경우의 수 라고 정의한다.

답은 $sum(dp[0][r][c]) (r,c: v[r][c] = target[0])$ 가 되겠다

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ll long long
#define ld long double
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpi;
typedef vector<vector<int>> vvi;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tlll;
typedef vector<ll> vl;
typedef vector<pair<ll, ll>> vpl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #if !defined(ONLINE_JUDGE)
  freopen("../input.txt", "r", stdin);
  freopen("../output.txt", "w", stdout);
  #endif // ONLINE_JUDGE

  int n, m, k;
  cin >> n >> m >> k;

  vs v(n);
  each(e,v) cin >> e;

  string target;
  cin >> target;

  vector<vvi> dp(target.size(), vvi(n, vi(m, -1)));

  function<int(int, int, int)> f = [&](int cur, int r, int c) {
    if (cur == target.size() - 1) {
      return 1;
    }
    auto& ret = dp[cur][r][c];
    if (ret != -1) return ret;

    ret = 0;
    for (int kk = 1; kk <= k; ++kk) {
      for (int dir = 0; dir < 4; ++dir) {
        int rr = r + kk * dr[dir];
        int cc = c + kk * dc[dir];
        if (rr < 0 || rr >= n || cc < 0 || cc >= m) continue;
        if (v[rr][cc] != target[cur + 1]) continue;
        ret += f(cur + 1, rr, cc);
      }
    }
    return ret;
  };

  int ans = 0;

  FOR(i, 0, n) FOR(j, 0, m) if (v[i][j] == target.front()) ans += f(0, i, j);

  cout << ans;
}

문제링크

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

풀이

$dp[i]$ 를 i 원으로 만들 수 있는 가장 큰 방 번호로 정의한다

• 방 번호가 최대 50자리까지 나올 수 있어서 string 으로 처리한다

$dp[i] = max(dp[j] + to\_string(k)) (j <= i , p[k] <= i - j)$

• 더 적은 금액 j 에서 k 번호 추가한 것들의 최대가 $dp[i]$

$O(M^2N)$ 으로 풀 수 있겠다

코드

원래 문자열은 길면 사전순으로 뒤에 있으므로 max_ 새로 정의해준다

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ll long long
#define ld long double
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpi;
typedef vector<vector<int>> vvi;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tlll;
typedef vector<ll> vl;
typedef vector<pair<ll, ll>> vpl;
typedef vector<vector<ll>> vvl;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)

string max_(string& s1, string& s2) {
  if (s1.length() > s2.length()) return s1;
  if (s1.length() < s2.length()) return s2;

  for (int i = 0; i < s1.size(); ++i) {
    if (s1[i] > s2[i]) return s1;
    if (s1[i] < s2[i]) return s2;
  }

  return s1;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  #if !defined(ONLINE_JUDGE)
  freopen("../input.txt", "r", stdin);
  freopen("../output.txt", "w", stdout);
  #endif // ONLINE_JUDGE

  int n;
  cin >> n;
  vi p(n);
  each(e, p) cin >> e;
  int m; 
  cin >> m;
  vector<string> dp(m + 1, "");

  for (int i = 0; i < dp.size(); ++i) {
    for (int j = 0; j <= i; ++j) {
      dp[i] = max_(dp[i], dp[j]);
      for (int k = 0; k < p.size(); ++k) {
        if (p[k] <= i - j) {
          string tmp = dp[j] + to_string(k);
          if (tmp.size() > 1 && tmp[0] == '0') tmp = tmp.substr(1);
          dp[i] = max_(dp[i], tmp);
        }
      }
    }
  }
  cout << dp[m];
}

문제링크

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

풀이

• DP using Bitfields
• 켜져있는 발전소 상태를 비트필드로 나타낸다.
• 지금 상태에서 한 발전소 키기 = min(켜져있는 발전소에서 꺼져있는 발전소 키기)

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int N;
  cin >> N;

  vector<vector<int> > cost(N, vector<int> (N));
  for (auto& e: cost) for (auto& ee: e) cin >> ee;

  string s;
  cin >> s;
  int num = 0;
  int tmp = 1;
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] == 'Y') {
      num |= tmp;
    }
    tmp <<= 1;
  }

  int P; cin >> P;
  int ans = 1e9;
  vector<int> dp(1 << s.size(), 1e9);
  dp[num] = 0;
  queue<pair<int, int> > q;

  q.push({num, dp[num]});
  auto countOnes = [&](int n) {
    int ones = 0;
    while (n) {
      if (n & 1) ones++;
      n >>=1;
    }
    return ones;
  };

  while (q.size()) {
    auto [f, d] = q.front();
    q.pop();
    if (dp[f] < d) continue;
    if (countOnes(f) >= P) {
      ans = min(ans, d);
      continue;
    }

    for (int i = 0; i < s.size(); ++i) {
      if ((f & (1 << i)) == 0) {
        int nn = f | (1 << i);
        int flag = false;
        for (int j = 0; j < s.size(); ++j) {
          if ((f & (1 << j))) {
            if (dp[nn] > d + cost[j][i]) {
              dp[nn] = d + cost[j][i];
              flag = true;
            }
          }
        }
        if (flag) q.push({nn, dp[nn]});
      }
    }
  }

  if (ans == 1e9) {
    cout << "-1\n";
  } else {
    cout << ans << '\n';
  }

}

문제링크

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

풀이

• 숫자 두개 또는 하나를 알파벳 하나로 해석할 수 있다.
• $dp[cur][l]$ : cur 위치에서 l 길이를 한 글자로 볼 때 경우의 수

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  string s;
  cin >> s;

  vector<vector<int> > dp(s.size(), vector<int> (3, -1));

  function<int(int, int)> f = [&](int cur, int l) {
    if (cur > s.size()) return 0;

    auto& ret = dp[cur][l];
    if (ret != -1) return ret;

    if (s[cur] == '0') return ret = 0;

    auto num = stoi(s.substr(cur, l));
    if (num > 26 || num <= 0) return ret = 0;

    if (cur + l == s.size()) return ret = 1;

    return ret = (f(cur + l, 1) + f(cur + l, 2)) % 1000000;
  };

  cout << (f(0, 1) + f(0, 2)) % 1000000 << '\n';
}

문제링크

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

풀이

• 자신의 w, h 보다 모두 큰 땅이 존재하면 그 땅은 그 큰 땅에 포함하여 사면 비용을 들이지 않고 사기 가능
• 그러한 땅들을 모두 제외하면 w 오름차순으로 정렬했을 때 h 는 내림차순으로 정렬됨
• i 번 땅과 j 번 땅을 같이 묶어서 사면, 그 사이에 있는 땅들은 포함해도 추가 비용 들지 않음
  • i번 땅과 묶인 땅들의 비용 = w[i] * h[j] 이므로
• 따라서, $dp[i]:$ i 번 땅까지 사는데 필요한 최소 비용이라고 정의하면
• $dp[i] = min_{0 \leq 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';
}

문제링크

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

풀이

• $dp[i]:$ i 번 나무를 완전히 자르는데 필요한 총 충전비용의 최솟값이라 하자
• $dp[i] = max_{0 <= 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';
}

문제링크

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

풀이

• $dp[i]:$ i 번 병사들로 특공대를 만들었을 때 조정된 전체 전투력의 최댓값이라고 하고
• $v[i], pv[i]$ 는 각각 병사의 전투력과 그 누적합 배열이라 하자
• $dp[i]$ 는 i 번 병사가 속해있는 특공대가 앞의 몇명을 포함하느냐에 따라서 생각해 볼 수 있고 그를 나타낸 점화식은 다음과 같다.
  • $dp[i] = max_{0 <= j  < i} (dp[j] + a * (pv[i] - pv[j])^2 + b * (pv[i] - pv[j]) + c)$
• 이를 정리하면 다음과 같다.
  • $dp[i] = max_{0 <= 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';
}

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

풀이

$dp[i][diff]:$ $i$ 까지 고려해서 쌓은 경우에서 차이가 $diff$ 일 때 더 높은쪽의 높이의 최댓값

※ $i, diff$ 이 불가능한 경우: $dp[i][diff] = -1$

$dp[i - 1][j] \neq -1$ 일 때

1. $i$ 블록 안 쌓는 경우
   • $dp[i][j] = max(dp[i][j], dp[i - 1][j])$
2. $i$ 블록 쌓는 경우
   1. 높은 쪽에 쌓는 경우
      • $dp[i][j + a[i]] = max(dp[i][j + a[i]], dp[i - 1][j] + a[i])$
   2. 낮은 쪽에 쌓는 경우
      1. $a[i] < j$
         • $dp[i][j - a[i]] = max(dp[i][j - a[i]], dp[i - 1][j])$
      2. $a[i] \geq j$
         • $dp[i][a[i] - j] = max(dp[i][a[i] - j], dp[i - 1][j] + a[i] - j)$

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<int> a(N);
    vector<vector<int> > dp(N, vector<int> (500001, -1));
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    
    dp[0][0] = 0;
    dp[0][a[0]] = a[0];
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j <= 500000; ++j) {
            if (dp[i - 1][j] == -1) continue;
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);
            if (j + a[i] <= 500000) dp[i][j + a[i]] = max(dp[i][j + a[i]], dp[i - 1][j] + a[i]);
            if (a[i] < j) {
                dp[i][j - a[i]] = max(dp[i][j - a[i]], dp[i - 1][j]);
            } else {
                dp[i][a[i] - j] = max(dp[i][a[i] - j], dp[i - 1][j] + a[i] - j);
            }
        }
    }
    if (dp[N - 1][0] > 0) {
        cout << dp[N - 1][0] << '\n';
    } else {
        cout << "-1\n";
    }
}