11058번: 크리보드

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


$O(n^2)$

i번 눌러서 가능 최대 A개수는
i-1번 누른 후 A 하나 더 출력하거나
j(j<=i-3)번 누른 상황을 복사하여 i-j-2번 출력하는 것이다.
dp[i]=max(dp[i-1]+1,max(j<i)(dp[j]*(i-j-1)))

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