HNU 12849 Flight Boarding Optimization

이 문 제 는 나 는 단지 선분 나무 와 사각형 의 최적화 만 생각 했 을 뿐이다. 사실은 사각형 의 최적화 없 이도 넘 을 수 있 지만 호수 대 OJ 는 넘 을 수 없다.
사실 이 문 제 는 선분 수 보다 더 좋 은 방법 으로 구간 [i, j] 의 비용 을 계산 하 는 것 이 있다.
구간 [i, j] 의 총 비용 은 w [i, j] 이 고 구간 [i, j] 이 j 에 게 주 는 비용 은 ss [i, j] 이 며 i 대 j 의 비용 은 c [i, j] 이다.
... 하면
w[i,j]= w[i,j-1]+ s[i,j]
s[i,j]= s[i+1, j]+ c[i,j]
선분 트 리 + 사각형 최적화 코드 O (n ^ 2logn + nk):

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 1010

struct node
{
	int l, r, sum;
}a[4*maxn];

int A[maxn], t[maxn][maxn];
int w[maxn][maxn], dp[maxn][maxn], xx[maxn][maxn];

void Build(int l, int r, int n)
{
	a[n].l= l;
	a[n].r= r;
	a[n].sum= 0;
	if(a[n].l== a[n].r)
		return;
	int mid= (a[n].l+ a[n].r)/ 2;
	Build(l, mid, 2*n);
	Build(mid+1, r, 2*n+1);
}

void add(int n, int v)
{
	if(a[n].l== v && a[n].r== v)
	{
		a[n].sum++;
		return;
	}
	int mid= (a[n].l + a[n].r)/ 2;
	if(v<= mid)
		add(2*n, v);
	else
		add(2*n+1, v);
	a[n].sum= a[2*n].sum+ a[2*n+1].sum;		
}

int query(int l, int r, int n)
{
	if(a[n].l== l && a[n].r== r)
		return a[n].sum;
	int mid= (a[n].l + a[n].r)/ 2;
	if(r<= mid)
		return query(l, r, 2*n);
	else if(l> mid)
		return query(l, r, 2*n+1);
	else
		return query(l, mid, 2*n)+ query(mid+1, r, 2*n+1);			
}

int main()
{
	int n, s, k;
	while(scanf("%d %d %d",&n,&s,&k)!=EOF)
	{
		Build(1, s, 1);
		memset(w, 0, sizeof w);
		memset(xx, 0, sizeof xx);
		for(int i= 1; i<= n; i++)
		{
			scanf("%d",&A[i]);
			add(1, A[i]);
			for(int j= 1; j< A[i]; j++)
				xx[j][A[i]]+= query(j, A[i]-1, 1);
		}
		for(int i= 1; i<= s; i++)
			for(int j= i+1; j<= s; j++)
				w[i][j]= w[i][j-1]+ xx[i][j];
		memset(dp, -1, sizeof dp);	
		for(int i= 1; i<= s; i++)
		{
			dp[i][1]= w[1][i];
			t[i][1]= 1;
			t[s+1][i]= s;
		}
		for(int j= 2; j<= k; j++)
			for(int i= s; i>= j; i--)
			{
				int aa= t[i][j-1];
				int bb= t[i+1][j];
				for(int u= aa; u<= bb; u++)
				{
					int temp= dp[u][j-1]+ w[u+1][i];
					if(dp[i][j]== -1 || temp< dp[i][j])
					{
						dp[i][j]= temp;
						t[i][j]= u;
					}
				}
			}
		printf("%d
",dp[s][k]);	
	}
	return 0;
}

좋 은 방법 O (n ^ 2 + nk):
코드:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 1010

int w[maxn][maxn], ss[maxn][maxn], dp[maxn][maxn];
int t[maxn][maxn], c[maxn][maxn];
int A[maxn];

int main()
{
	int n, k, s;
	while(scanf("%d %d %d",&n,&s,&k)!=EOF)
	{
		memset(c, 0, sizeof c);//   i j    
		memset(ss, 0, sizeof ss);//  [i,j]  j    
		memset(w, 0, sizeof w);//    [i,j]     
		for(int i= 1; i<= n; i++)
		{
			scanf("%d",&A[i]);
			for(int j= 1; j<= i; j++)
				if(A[j]< A[i])
					c[A[j]][A[i]]++;
		}
		for(int j= 1; j<= s; j++)
			for(int i= j; i> 0; i--)
				ss[i][j]= ss[i+1][j]+ c[i][j];
		for(int i= 1; i<= s; i++)
			for(int j= i; j<= s; j++)
				w[i][j]= w[i][j-1]+ ss[i][j];	
		
		memset(dp, -1, sizeof dp);	
		for(int i= 1; i<= s; i++)
		{
			dp[i][1]= w[1][i];
			t[i][1]= 1;
			t[s+1][i]= s;
		}
		for(int j= 2; j<= k; j++)
			for(int i= s; i>= j; i--)
			{
				int aa= t[i][j-1];
				int bb= t[i+1][j];
				for(int u= aa; u<= bb; u++)
				{
					int temp= dp[u][j-1]+ w[u+1][i];
					if(dp[i][j]== -1 || temp< dp[i][j])
					{
						dp[i][j]= temp;
						t[i][j]= u;
					}
				}
			}
		printf("%d
",dp[s][k]);			
	}
	return 0;
}