oVeron

해당 그래프를 위상 정렬하여 진입 차수가 0인 모든 정점에 바이러스를 풀면 될 것이다.그런데 이 그래프는 사이클이 존재할 수 있으므로, SCC를 이용해 사이클을 묶어 줘야 한다.SCC를 만들고 위상 정렬해 진입 차수가 0인 정점의 개수를 찾으면 된다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAXN = 100000;int N, M;vector graphf[MAXN], graphr[MAXN];bool vis[MAXN];stack st;vector> SCC;int SCCnum[MAXN]; //정점 i의 SCC 번호vector graphSCC[MAXN..

알고리즘/baekjoon 2024. 9. 1. 11:15

1.\(k\)번 수열을 나눠 그 나눈 값을 최대화해야 하는 문제이다. 만약 우리가 수열의 특정한 구간을 임의의 횟수만큼 나눴을 때의 최댓값을 알고 있다면, 해당 구간을 포함하는 큰 구간의 최댓값을 구하는 데 그 최댓값을 이용할 수 있으므로, 이 문제는 DP를 이용해 풀 수 있다. 대략적인 DP식은 다음과 같을 것이다. \(dp[i][j] = \) 수열에서의 구간 \([i, j]\)에서의 최댓값$ dp[i][j] = \sum_{k=i}^{j-1} dp[i][k] + dp[k+1][j] $ 풀어야 하는 부분 문제는 \(O(n^2)\)개인데 각 부분 문제의 반복문 횟수는 \(O(n)\)이므로, 전체 시간 복잡도는 \(O(n^3)\)이다. 시간을 더 줄일 방법을 찾아야 한다. 2.수열을 세 부분으로 나누었을 때..

알고리즘/baekjoon 2024. 8. 17. 14:23

DP Knuth Optimization 기본 문제.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int INF = 1e9;const int MAXK = 5001;int K;int dp[MAXK][MAXK];int pos[MAXK][MAXK];int psum[MAXK];void solve(){ fill(&dp[0][0], &dp[MAXK-1][MAXK], INF); cin >> K; for(int i=1; i> fi; dp[i][i] = 0; pos[i][i] = i; psum[i] = psum[i-..

알고리즘/baekjoon 2024. 8. 15. 22:53

1.producer company에게 widget을 사서 consumer company에게 팔아 최대한 많은 이익을 내야 하는 문제이다. 그 이익을 식으로 나타내면 \((\) \(q_j - p_i\) \()\) \(*\) \((\) \(e_j - d_i\) \()\) 가 된다.이때 \((\) \(q_j,  p_i\) \(),\)  \((\) \(e_j, d_i\) \()\)를 좌표평면에서의 점이라 생각하면, 이 문제는 \((\) \(q_j,  p_i\) \(),\) \((\) \(e_j, d_i\) \()\)가 이루는 직사각형의 넓이의 최댓값을 구하는 문제와 같다. 2.임의의 두 정수 \(a, b\)에 대하여 \(p_a \leq p_b, d_a \leq d_b\)라면, \((\) \(p_b, d_b\) ..

알고리즘/baekjoon 2024. 8. 15. 19:41

김치를 넣는 날을 \(i\), 꺼내는 날을 \(j\)라 하면, 김치의 맛은 다음 식과 같다. \(T_j * (j - i) + V_i\)  (\(i  다음 식은 사각 부등식을 만족하므로(사각 부등식에 직접 대입해보면 알 수 있다), DnC Opt를 사용할 수 있다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAXN = 100001;int N, D;ll T[MAXN], V[MAXN];ll ans = 0;void solve(int s, int e, int l, int r){ if(l > r) return; int m = (l + r) ..

알고리즘/baekjoon 2024. 8. 14. 07:44

DP - Divide and Conquer Optimization 기본 문제#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const ll INF = 1e18;const int MAXL = 8001;const int MAXG = 801;int L, G;ll psum[MAXL];ll dp[MAXG][MAXL]; //dp[i][j] : i번째 간수까지 j번째 칸을 감시할 때 탈옥 위험도의 최솟값//s, e : dp[i][m]를 최소로 만들어 주는 위치 opt의 범위void solve(int s, int e, int l, int r, int i){ if(l > r) re..

알고리즘/baekjoon 2024. 8. 13. 19:42

Centroid Decomposition(센트로이드 분할) 기본 문제.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int INF = 1e9;const int MAXN = 100001;int N;int c[MAXN];vector graph[MAXN];int subSize[MAXN];bool cache[MAXN]; //cache[u] : 정점 u가 centroid가 되었는지를 확인한다.void buildSubSize(int u, int p) //정점 u를 root로 하는 서브트리의 크기를 DFS를 이용해 구한다.{ subSize[u] = 1; for..

알고리즘/baekjoon 2024. 8. 13. 12:51

HLD 세그먼트 트리 기본 문제.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;#define F first#define S secondconst int MAXN = 100001;int N, M;vector graph[MAXN];pii edge[MAXN];int SubSize[MAXN];int DFS_cnt = 1;int DFS_num[MAXN];int chain_lv[MAXN], chain_head[MAXN], chain_par[MAXN];//lv : chain의 깊이, head : chain을 대표하는 노드 번호, par : chain의 부모 노드int segTree..

알고리즘/baekjoon 2024. 8. 12. 23:34