[일반] 이 문제 풀이 아시는분

[익명(182.231)]

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

아무리 봐도 O(n^6)밖에 못짜겠는데 혹시 O(n^4)이하 풀이 아시는분 계신가요?

[대학원오지마세요(publfl)]

안풀어보긴 했는데 당장 생각나는건 테이블 크기 2NS, 각 테이블 채우는데 NS시간이 걸려 총 연산수는 2N^2S^2이 되는 DP정도 생각이 나는데 맞는지는 잘 모름

[익명(223.33)]

저는 dp상태식을 i개의 원소로 이루어진 배열로 만들어지는 점수 w이하인 카르테시안 트리의 가짓수로 정의했는데 dp테이블 어떻게 정의하셨나요?