2022.05.09 PS 일지

냠

굉장한 학생

문제 링크

풀이

각 학생은 $(a,b,c)$값을 지닌다. 만약 모든 다른 $(a',b',c')$에 대해 $a'>a,\ b'>b,\ c'>c$가 만족한다면 굉장하다.

따라서 $(a,b,c)$를 $a$에 대한 오름차순으로 정렬한 뒤, $\text{RMQ}$ 세그트리에서 $b$번 인덱스에 $c$를 넣는 식으로 관리하면 문제를 풀 수 있다.

List of Unique Numbers

문제 링크

$\text{last_pos}[x]$를 관리하면서 풀면 된다.

정사각형 만들기

문제 링크

정확한 내용을 모르겠어서 디코에 질문 올렸다.

풀이

 

코드

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i=(a); i<=(b); ++i)
#define mup(x,y) x = min(x,y)

const int N = 10003, M = 103;
int n, m;
int dp[N][M];

int main() {
    cin >> n >> m;
    if (n < m) swap(n,m);
    rep(i,1,n) rep(j,1,m) {
        dp[i][j] = 1e9;
        if (i == j) dp[i][j] = 1;
        else if (j*j <= 3*i) dp[i][j] = dp[i-j][j]+1;
        else {
            rep(k,1,i/2) mup(dp[i][j],dp[k][j]+dp[i-k][j]);
            rep(k,1,j/2) mup(dp[i][j],dp[i][k]+dp[i][j-k]);
        }
    }
    cout << dp[n][m];
}