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