📝 문제 정보#
🧐 관찰 및 접근#
- 서브태스크가 상당히 많고, 문제가 쉽지 않아보인다. 차근차근 해보자.
- $N = 3$
- 브루트포스에 가깝게 풀 수 있을 것 같다.
- 문자는 어차피 최대 3개 존재하므로, 3개에 대해 $X$가 가질 수 있는 경우의 수 $3^3$가지, $Y$가 가질 수 있는 경우 $3^3$가지를 전이하면서 다익스트라로 풀 수 있을 것 같다.
- ㅇㅋ 된당
- $S_i = a$
- 모든 문자가 a라면?
- $X$에 들어있는 문자 개수, $Y$에 들어있는 문자 개수 두가지를 이용해서 $N^2$ 정점 다익스트라가 가능해보인다.
- $N \leq 30$
- 이제부터 진짜로 어떻게풀어야하는지 고민해봐야할 것 같은데…
- 일단 복사할 문자 $Y$는 $X$의 substr이어야할 것이다.
- 그럼 $Y$가 될 수 있는 경우의수는 $O(N^2)$이고
- $X$를 만들때든, $Y$를 만들기위해 빌드업하고 있을때든 결국 $X$도 $X$의 substr로 존재해야한다.
- 이것도 경우의수가 $O(N^2)$ 인 것 같다.
- $Y$를 붙일 수 있는지 검사하는? 그런것들이 전처리를 안하면 $O(N)$쯤 되어보이니, 아마 종합해서 $O(N^5)$정도로 풀 수 있지 않나?
- 근데 DP 전이식이 헷갈린다. 이게 상호 참조가 없나? 비용들이 달라서 다익으로 해야될 것 같은데.
- 일단 복사할 문자 $Y$는 $X$의 substr이어야할 것이다.
- $\text{DP}[x][y]$: 현재 $X$에 $x$, $Y$에 $y$가 들어있다고 하자.
- $A$ 연산을 거치면 $x$에 한개가 붙고, $y$는 그대로다.
- $B$ 연산을 거치면 $x$가 빈 문자열이 되고, $y$는 $x$의 값으로 갱신된다.
- $C$연산을 거치면 $x = x + y$가 되고, $y$는 그대로다.
- 아하, 생각보다 $y$가 갱신될일이 없다. 그리고 $y$가 갱신된다면 $x$가 빈 문자열이 된 상태에서 시작한다!
- 복사하고 붙여넣는 과정을 그냥 해버렸다고 생각하는게 더 쉬울 것 같다.
- $\text{DP}[i][j]$ : $S_i$~$S_j$까지 만드는 최소비용이라고 하자.
- 이건 $\text{DP}[i][j-1]$ 후 $A$연산을 하거나
- 어떤 $i \leq i', j' \leq j$가 있어서 그친구를 복사한 후 붙여넣기를 여러번 하거나.
- 이건 그리디하게 되는듯? 한번 짜보자.
- 오!!! 이걸로 대충 $30^5$정도는 성공했다!
- $\text{DP}[i][j]$ : $S_i$~$S_j$까지 만드는 최소비용이라고 하자.
- 이제부터 진짜로 어떻게풀어야하는지 고민해봐야할 것 같은데…
- $N \leq 200$
- 이제 $O(N^4)$는 16억이니 빡세고, $O(N^3\log{N})$쯤 까지는 줄여야하는데…
- 섭태 5는 세제곱, 섭태 6은 제곱로그겠다.
- 음, 위에서 했던 관찰대로 $Y$에 복사해서 넣으면 $X$는 초기화돼서 시작하므로, DP를 $B$연산으로 $Y$에 복사한거까지 했을 때를 기준으로 하자.
- 젤 중요한거는 저 그리디하게 비교하면서 뒤로 슝슝슝 가는 파트인 것 같다.
- 이제 $O(N^4)$는 16억이니 빡세고, $O(N^3\log{N})$쯤 까지는 줄여야하는데…
💻 풀이#
- 코드 (C++):
void solve(){
cin >> N >> S >> A >> B >> C;
if(N >= mxN) {
cout << -1 << "\n";
return;
}
rep(i, 0, N+1) rep(j, 0, N+1) DP[i][j] = LLONG_MAX;
rep(i, 0, N+1) rep(j, i+1, N+1) DP[i][j] = A * (j-i) + B;
const mint base = 131;
const mint2 base2 = 137;
vector<mint> hsh(N+1), pw(N+1);
vector<mint2> hsh2(N+1), pw2(N+1);
hsh[0] = 0; pw[0] = 1;
hsh2[0] = 0; pw2[0] = 1;
rep(i, 0, N){
hsh[i+1] = hsh[i] * base + S[i];
pw[i+1] = pw[i] * base;
hsh2[i+1] = hsh2[i] * base2 + S[i];
pw2[i+1] = pw2[i] * base2;
}
auto getHash = [&](int l, int r) -> pair<ll, ll>{
ll ret1 = (hsh[r] - hsh[l] * pw[r-l]).get();
ll ret2 = (hsh2[r] - hsh2[l] * pw2[r-l]).get();
return {ret1, ret2};
};
ll ans = N*A;
rep(L, 1, N+1){
// A 연산 앞뒤에 붙여서 전이할 때
if(L >= 2) rep(s, 0, N){
if(s+L > N) break;
int e = s+L;
DP[s][e] = min(DP[s][e], DP[s+1][e]+A);
DP[s][e] = min(DP[s][e], DP[s][e-1]+A);
}
// 해당 문자열을 복사하는 최소 비용
map<pair<ll,ll>, vector<int>> mp;
rep(s, 0, N){
if(s+L > N) break;
int e = s+L;
mp[getHash(s, e)].push_back(s);
}
// 복사 연산으로 전이
for(auto& [_, v]: mp){
int sz = v.size();
ll mn = 1e18;
for(auto s: v) mn = min(mn, DP[s][s+L]);
// 다음에 갈 수 있는 위치
vector<int> nxt(sz, sz);
for(int i = 0, j = 0; i < sz; i++){
while(j < sz && v[j] < v[i]+L) j++;
nxt[i] = j;
}
rep(i, 0, sz){
int s_pos = v[i];
int cidx = i;
int cnt = 0;
while(cidx < sz){
cnt++;
int e_pos = v[cidx]+L;
if(e_pos > N) break;
DP[s_pos][e_pos] = min(DP[s_pos][e_pos], mn + (C * cnt) + ((e_pos - s_pos) - (L * cnt)) * A + B);
cidx = nxt[cidx];
}
}
}
}
ans = min(ans, DP[0][N] - B);
cout << ans << "\n";
}