11058 - 크리보드

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

출력 결과에 영향을 미치는 연산이 A를 그냥 누르는 거랑(+1), Ctrl-V (+복사했던 크기) 인데 클립보드에 복사해놓은 크기때문에 재귀로 짜는데 애를 먹었다.

복사한 크기만큼 늘어나기 때문에, Ctrl-V 를 하기 위해서는 이전에 Ctrl-A, Ctrl-C 가 꼭 필요하다.

문제에 적힌 연산을 순서대로 A, S, C, V 라고 한다면 $N=6$인 경우는 아래와 같이 가능하다.

AAAAAA
AAASCV
AASCVV
ASCVVV

이 정도가 의미있는 타이핑인거같다. 타이핑을 n번한 것을 $f(n)$이라 하자. 그럼 위 4줄은 각각 $f(5)+1$, $f(3)*2$, $f(2)*3$, $f(1)*4$ 이다.

$$f(0) = 0, f(n) = \begin{cases} f(n-1) + 1, \\ f(k) * (n-k-1), & \text{if $k$ < n - 4 } \end{cases}$$

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

int main(){
    int n;
    scanf("%d", &n);
    lld dp[101]={0};
    for(int i=1; i<=n; ++i){
        dp[i] = dp[i-1]+1;
        for(int k=n-3; j>=0; --j){
            dp[n] = max(dp[n], dp[k] * (n-k-1));
        }
    }
    printf("%lld", dp[n]);
    return 0;
}