ryute   5년 전

다음 코드와 같이 문제를 해결하려 했습니다. 나눈 순서와 상관 없이 나눈 각 부분의 합을 S1,S2,S3,...,Sk+1이라고 하면 최종적으로 얻는 점수가 S1*(S2+S3+...+Sk) + S2*(S3+S4+...Sk) + ... Sk-1*Sk 인 것 같은데 이게 모든 경우에 성립하는지 궁금합니다.

또 혹시 만약 위 식이 성립한다면, S[i]가 1~i까지의 합일 때
D[k][n]=1~n번째 수를 적절히 k번 잘라 얻을 수 있는 최대 점수라고 정의했을 때
D[k][n]=max(i=1 to n-1) D[k-1][i]+S[i]*(S[n]-S[i])
=max(i=1 to n-1) S[i]*S[n]+D[k-1][i]-S[i]*S[i]
로 나타낼 수 있는지, 그리고 만약 저 점화식에 오류가 없다면 모든 k에 대해서 CHT를 이용한 DP를 적용해서 해결하는 것이 맞는 풀이인지 궁금합니다.

현재 코드로는 oj.uz에서 채점했을 때 역추적은 둘째치고 최댓값 자체도 제대로 찾지 못하는 경우가 있는 것 같습니다. ㅠㅠ

imeimi2000   5년 전

기울기가 같은 직선이 연속으로 들어오면 어떻게 될까요

ryute   5년 전

동일한 기울기를 가지는 직선이 연속해서 들어왔을 때 두 직선이 동시에 스택에 존재하는 문제가 있었고, 만약 동일한 기울기를 가진 두 직선이 연속으로 존재한다면 y절편이 더 큰 직선만을 남기도록 변경했습니다. 이렇게 수정했더니 답 자체는 잘 나오는 것 같습니다.

문제가 되는 것은 답 역추적 부분인데, 0이 연속해서 들어오는 경우에 어디를 잘라야 하는지 판별하기가 상당히 난감해진다는 것을 깨달았습니다. 일단 같은 직선이 여러개 존재해서 어떤 부분을 자르던 간에 문제가 없다면 가장 왼쪽 부분을 자른 다음, 동일한 위치를 자른다면 자르는 위치를 한 칸 오른쪽으로 이동시켜 자르려고 하였지만 (주석이 있는 부분) 잘 작동하지 않습니다. 이 부분에서 조언 하나만 해주시면 감사하겠습니다.

imeimi2000   5년 전

DP식을 생각해보면 ans[i]==ans[i+1]인 상황이 나올리가 없습니다.

51행에 here=pre[k-i+1][here];을 쓰셔야 하지 않을까요

ryute   5년 전

헉 그러네요

정말정말 감사드립니다

imeimi2000   5년 전

이 문제에서는 자르지 않는 경우가 무조건 손해라서 문제가 안 생겼지만, DP[i][0]가 0이 아니고 impossible이기 때문에 처음에 0x+0을 넣는 것은 위험해보이네요

ryute   5년 전

그러면 impossible인 케이스에서는 기울기가 0이고 y절편이 -INF인 직선을 넣어주면 되는건가요?

imeimi2000   5년 전

그러면 되겠죠

댓글을 작성하려면 로그인해야 합니다.