DP 가지치기
3768 단어 dp
N단을 동쪽으로 염색하려면 매번 한 구간에 염색을 하는데 필요한 비용은 이 구간의 색깔 총수의 제곱이다.단락마다 한 번만 염색할 수 있다.최소 비용을 들여 모든 구간을 염색하세요.N<=500000;
이 문제도 방정식을 생각하기 쉽다. F[j]는 전 i단의 최소 비용을 표시하고 F[j]=min{F[k]+sum[k+1][j]}(k
최적화 B: 예를 들어 데이터 3, 4, 2, 4, 2, 4, 3, 2, 2.현재 F[9]를 요구하고 있으며, k를 6으로 줄일 때 마지막 염색 구역은 [4 3 2 2]이다.세 가지 색깔이 있다면 너무 손해다.이전에는 [342442]였기 때문에 이것들을 함께 바르면 여전히 3^2의 대가였지만 앞의 숫자가 줄어들었다. 분명히 이런 것이 더 좋았다.그래서 F[i]를 구할 때 앞의 색깔이 [......]라고 가정한다.xxyx], 그러면 k가 왼쪽에 있는 x의 위치로 들어올 때 마지막으로 그 x도 같이 칠하는 것보다 못할 것이다. 즉, k가 z까지 들어올 때보다 낫지 않을 것이다.그래서 왼쪽의 x를 삭제할 수 있고, 구체적으로 삭제하면 양방향 체인 시계를 사용한다.즉 x가 여러 개 있다면 가장 오른쪽에 있는 x만 보존하면 된다.
최적화된 핵심 코드:
1 dp[0] = 0, pre[0] = -1; 2 for (int i = 1; i <= n; i++) { 3 if (!mp.count(a[i])) mp[a[i]] = i; 4 else { 5 int id = mp[a[i]]; 6 nxt[pre[id]] = nxt[id]; 7 pre[nxt[id]] = pre[id]; 8 mp[a[i]] = i; 9 } 10
11 int cnt = 0; 12 for (int j = pre[i]; j != -1; j = pre[j]) { 13 cnt++; 14 dp[i] = min(dp[i], dp[j] + cnt * cnt); 15 if (cnt * cnt > i) 16 break; 17 } 18 }코드 출처 참조http://www.2cto.com/kf/201410/340390.html
좋은 웹페이지 즐겨찾기
