Beyond the Void
BYVoid
Ural 1167 Bicoloured Horses
本文正體字版由OpenCC轉換

動態規劃,由於是馬進入馬廄連續的,要先預處理求出每個連續序列的馬進入一個馬廄的不快樂值。然後以O(N^2*K)時間複雜度DP。

設A[0][i]爲前i匹馬中種類爲0的馬的數量,A[1][i]爲前i匹馬中種類爲1的馬的數量。則一個區間[i,j]內的馬進入一個馬廄的不快樂度U[i,j]爲 U[i,j]=( A[0][j] - A[0][i-1] ) * ( A[1][j] - A[1][i-1] )

動態規劃狀態設定 F[i,j]表示前i個馬廄,進入前j匹馬的最小不快樂度。

狀態轉移方程 F[i,j]=min{ F[i-1,k] + U[k+1,j] | k=0..j-1 }

邊界條件 F[0,0]=0 F[0,i]=MAX (i=1..N)

目標解 F[K,N]

以下是程序代碼

#include <iostream>

using namespace std;

const int MAX=501;
const int INF=0x7FFFFFF;

int N,K;
int Q[MAX],A[2][MAX];
int F[MAX][MAX];

void init()
{
	int i;
	freopen("1167.in","r",stdin);
	freopen("1167.out","w",stdout);
	scanf("%d%d",&N,&K);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&Q[i]);
		A[0][i]=A[0][i-1];
		A[1][i]=A[1][i-1];
		if (Q[i]==0)
			A[0][i]++;
		else
			A[1][i]++;
		F[0][i]=INF;
	}
}

inline int U(int i,int j)
{
	return (A[0][j]-A[0][i-1])*(A[1][j]-A[1][i-1]);
}

void dynamic()
{
	int i,j,k,t,min,u;
	for (i=1;i<=K;i++)
	{
		for (j=1;j<=N;j++)
		{
			min=INF;
			for (k=0;k<=j-1;k++)
			{
				u=U(k+1,j);
				t=F[i-1][k] + u;
				if (t<min)
					min=t;
			}
			F[i][j]=min;
		}
	}
}

int main()
{
	init();
	dynamic();
	cout << F[K][N] << endl;
	return 0;
}

上次修改時間 2017-02-03

相關日誌