[알고리즘 입문] 단조로운 대기열 최적화 동적 기획: [RomaniaOI2002]Fence

Problem
Description A team of k (1 <= K <= 100) workers should paint a fence which contains N (1 <= N <= 16 000) planks numbered from 1 to N from left to right. Each worker i (1 <= i <= K) should sit in front of the plank Si and he may paint only a compact interval (this means that the planks from the interval should be consecutive). This interval should contain the Si plank. Also a worker should not paint more than Li planks and for each painted plank he should receive Pi $ (1 <= Pi <= 10 000). A plank should be painted by no more than one worker. All the numbers Si should be distinct. Being the team’s leader you want to determine for each worker the interval that he should paint, knowing that the total income should be maximal. The total income represents the sum of the workers personal income. Write a program that determines the total maximal income obtained by the K workers. Input The input contains: Input N K L1 P1 S1 L2 P2 S2 … LK PK SK Semnification N -the number of the planks; K ? the number of the workers Li -the maximal number of planks that can be painted by worker i Pi -the sum received by worker i for a painted plank Si -the plank in front of which sits the worker i Output The output contains a single integer, the total maximal income. Sample Input 8 4 3 2 2 3 2 3 3 3 5 1 1 7 Sample Output 17
Solution

이 문제를 받은 후에si에 대한 순서는 일정하다.이렇게 해야만 알고리즘의 질서성을 보장할 수 있다.

이 문제에 대해 가장 간단한 DP를 고려하고 f[i][j]f[i][j]f[i][j][j]를 전 i명의 목수로 설정하여 j개의 널빤지를 칠하는 최대 수익을 얻는다.

① ① ① ① iii의 목수가 한 조각도 칠하지 않을 경우: f[i] [j] = f [j] = f [i] [i1] [j] [j] [j] f[i] [j]: f[i] [j] = f[i] [j] [j] = f[i[i] [j] ② ② ii의 목수가 j 블록을 칠하지 않을 경우: f [i] [i] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j③③ ③ 제ii 블록 목수가 제jj 블록을 칠할 때,제 k+1k+1k+1 블록 브러시에서 jjj: 이때 위치 관계를 만족시켜야 한다. k+1≤S i≤jk+1≤Si≤jk+1≤Si≤jk+1≤Si≤j;길이 관계도 충족: j -3 k ≤ L j-k ≤ L j -3 k ≤ L.방정식: f[i] [j] = m in(f [i 1] [k] + (j i] [i] [k] + (j i] [j i] [j] pi) (j - I I I I I I I I I = f[k] + (j: k] + (j-k) i)) (j - I I I I ≤k ≤S-1, j ≥si) 1 1, j 1, j 1, j 1] [i] [j] = min(f[i] = min(f [i] [j] [j] [j] [j] [j] [j] [j] [j] [j] [[j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] [j] --1, j≥si)

시간 복잡도: O(N 2 K) O(N^2 K) O(N2 K)

우리는 상황 ③③③에 대한 최적화를 고려했다

f [ i ] [ j ] = m i n ( f [ i − 1 ] [ k ] + ( j − k ) ∗ p i ) f[i][j]=min(f[i-1][k]+(j-k)*pi) f[i][j]=min(f[i−1][k]+(j−k)∗pi) → f [ i ] [ j ] = m i n ( f [ i − 1 ] [ k ] + j ∗ p i − k ∗ p i ) →f[i][j]=min(f[i-1][k]+j*pi-k*pi) →f[i][j]=min(f[i−1][k]+j∗pi−k∗pi) → f [ i ] [ j ] = j ∗ p i + m i n ( f [ i − 1 ] [ k ] − k ∗ p i ) (이때 i, j는 상수로 볼 수 있음)→f[i] [j] = j*pi+min(f[i-1] [k]-k*pi)→→f[i] [j] [j] = j*pi+min([i-1][i-1] [k]-k***pi))(이때 i, j는 상수로 볼 수 있음)→f[i[i] [i] [j] [j][i] [j] [j] [j] [j]=min(f[j] [iiii-1] [[k][k]-k]-k*pi))))(이때 i, j, j는 상수로 볼 수 있음))(이때 i, j는 상수로 볼 수 있음) 이때 i, j는 상수로 볼 수 있음) 이때 만족(j는 상량으로 ≤ Si -3 1, j ≥si)

각 kk에 대해 우리는 그 하계 j-L i j-Li j-Li는 j가 커지면서 커지고 상계 S-i -1 Si-1 Si-1은 변하지 않는다는 것을 발견했다.이때 모든 kkk는 하나의 정책 결정의 값에 대응한다.그리고 현재의 jjjj가 어떤 kkk를 버린 후에 뒤의 jjjj도 이 결정을 사용하지 못한다.따라서 우리는 이 결정의 최우수치를 유지하기 위해 낮은 순서의 단조로운 대열을 사용할 수 있다.

이 문제에 대한 구체적인 방법은 다음과 같다. S t e p 1 Step1 Step1: 모든 의사 결정을 단조로운 대기열에 넣고 의사결정의 단조성을 유지한다.S t e p 2 Step2 Step2: j를 열거할 때 잘못된 헤더를 삭제합니다.S t e p 3 Step 3 Step 3: 대기열이 비어 있지 않을 때 헤더를 가져와 상태 이동합니다.

코드는 다음과 같다:

#include
#include
#include
#include
using namespace std;
struct node{int l,p,s;};
node a[200];
int N,K,t,h;
int L[200],P[200],S[200],f[200][50000],q[50000];
inline bool cmp(node a,node b)
{
	if (a.s<b.s) return true;
	return false;
}
#define val(i,k) (f[i-1][k]-k*P[i])
int main(void)
{
	cin>>N>>K;
	for (int i=1;i<=K;++i)
	    cin>>a[i].l>>a[i].p>>a[i].s;
	sort(a+1,a+K+1,cmp);
	// si     
	for (int i=1;i<=K;++i)
	    L[i]=a[i].l,P[i]=a[i].p,S[i]=a[i].s;
	//     
	    
	for (int i=1;i<=K;++i)
	{
		for (int j=max(0,S[i]-L[i]);j<=S[i]-1;++j)
		{
			while (h<=t && val(i,j)>=val(i,q[t])) --t;
			q[++t]=j;
		}
		//        
		
		for (int j=1;j<=N;++j)
		{
			f[i][j]=max(f[i-1][j],f[i][j-1]);
			// 1,2         
			
			if (j<S[i]) continue;
			
			while (h<=t && q[h]<j-L[i]) h++;
			//       
			if (h<=t) f[i][j]=max(f[i][j],f[i-1][q[h]]+(j-q[h])*P[i]);
			// 3         
		}
	}
	cout<<f[K][N]<<endl;
	return 0; 
} 

마지막으로 단조로운 대기열 최적화 상황을 정리했다. 상태 이동 방정식은 다음과 같다. f[i]=m in(f[j]+v al(i, j), L(i)≤j≤R(i) f[i]=min(f[j]+val(i, j), L(i)≤j≤R(i) f[i]=min(f[j]+val(i, j), L(i)≤jj≤R(i) 중 상하계의 변화가 있다.다항식 v a l (i, j) val (i, j) val (i, j) 의 모든 단항식은 i i 개 j j 중의 한 항목만 관련될 수 있고 i i 와 j j의 곱셈 항목을 동시에 포함할 수 없습니다.이것이 바로 단조로운 대열 최적화다.본문에 만약 누락되거나 잘못된 점이 있으면 독자의 지적을 환영합니다.