Ural 1167 Bicoloured Horses
动态规划，由于是马进入马厩连续的，要先预处理求出每个连续序列的马进入一个马厩的不快乐值。然后以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