7cf3c028e2f206a26d81f6ec448274



1 기억안남 개좆밥

2 기억안남 개좆밥

3 스택


4번 dp아님


지금 지점에서 이전 지점의 상태에 따라 관계식을 세우는게 dp인데

연승때문에 이전 지점의 상태의 개수가 존나많아서 안댐



내가푼방법은 이거임


1. 이번에 이길 수 있으면 최대 연승할 수 있는 데까지 연승땡겨봄

2-1. 1에서 최대 연승으로 땡긴 합이 k*개수보다 크면 그 합을 더하고, 연승 마지막의 다음 번호로 넘어감

2-2. 1에서 최대 연승으로 떙긴 합이 k*개수보다 작으면 이 시점에선 져야만 함. 따라서 k만 더하고 이번번호의 다음으로 넘어감

3. 반복


처음엔 2-2에서 최대연승으로 떙긴 합보다 k*개수가 작으면 걍 k*개수 더해주고 마지막번호 다음으로 넘어가면 되는줄 알았음

이러면 O(n) 나와서 20만개도 문제없거든

근데 생각해보니까 지금 당장 지는게 이득이더라도 다음번호까지 질필욘 없더라고

반례가 이거임

{ 1, 1, 1, 10, 1, 1, 1, 1, 1, 1, 1, 1 }, 2, 5 //답:73


근데 문제가 이 풀이는 최악의경우 (모두 이길 수 있는데 져야하는 경우)엔 O(n^2)인데

n 범위가 20만까지라서 안뚫려야될거같은데 뚫리더라


O(n) 풀이 아는사람 있으면 좀알려주라