「RQNOJ272」马棚问题

2013年11月25日3,1950

题目描述

每天，小明和他的马外出，然后他们一边跑一边玩耍。当他们结束的时候，必须带所有的马返回马棚，小明有K个马棚。他把他的马排成一排然后跟随它走向马棚，因为他们非常疲劳，小明不想让他的马做过多的移动。因此他想了一个办法：将马按照顺序放在马棚中，后面的马放的马棚的序号不会大于前面的马放的马棚的序号。而且，他不想他的K个马棚中任何一个空置，也不想任何一匹马在外面。已知共有黑、白两种马，而且它们相处得并不十分融洽。如果有i个白马和j个黑马在一个马棚中，那么这个马棚的不愉快系数将是i*j。所有k个马棚不愉快系数的和就是系数总和。确定一种方法把n匹马放入k个马棚，使得系数总和最小。

输入格式输入：在第一行有两个数字：n（1≤n≤500）和k（1≤k≤n）。在接下来的n行是n个数。在这些行中的第i行代表队列中的第i匹马的颜色：1意味着马是黑色的，0意味着马是白色的。

输出格式输出：只输出一个单一的数字，代表系数总和可能达到的最小值。

样例输入

6 3 {6匹马，3个马棚}
1 {第1匹马为黑马}
1
0 {第3匹马为白马}
1
0
1

样例输出

2 {最小系数总和}

#include<cstring>
#include<iostream>
using namespace std;
int b[501]={0},w[501]={0},t;
int value(int x,int y)
{
    return (b[y]-b[x])*(w[y]-w[x]);
}
int main()
{
    int n,m,a[501],f[501][501];
	memset(f,127,sizeof(f));
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
	   cin>>t;
	   if(t==1){b[i]=b[i-1]+1;w[i]=w[i-1];}
	   else {b[i]=b[i-1];w[i]=w[i-1]+1;}
	}
	f[0][0]=0;
	for(int j=1;j<=m;j++)
	   for(int i=j;i<=n;i++)
	      for(int k=j-1;k<=i-1;k++)
			 f[i][j]=min(f[i][j],f[k][j-1]+value(k,i));
	cout<<f[n][m];
	return 0;
}

#include<cstring>

#include<iostream>

using namespace std;

int b[501]={0},w[501]={0},t;

int value(int x,int y)

{

return (b[y]-b[x])*(w[y]-w[x]);

}

int main()

{

int n,m,a[501],f[501][501];

memset(f,127,sizeof(f));

cin>>n>>m;

for(int i=1;i<=n;i++)

{

cin>>t;

if(t==1){b[i]=b[i-1]+1;w[i]=w[i-1];}

else {b[i]=b[i-1];w[i]=w[i-1]+1;}

}

f[0][0]=0;

for(int j=1;j<=m;j++)

for(int i=j;i<=n;i++)

for(int k=j-1;k<=i-1;k++)

f[i][j]=min(f[i][j],f[k][j-1]+value(k,i));

cout<<f[n][m];

return 0;

}

« 「JoyOI1048」田忌赛马「JoyOI1091」等差数列 »

hzwer.com _ Home | http://hzwer.com

「RQNOJ272」马棚问题

分类目录

热门文章

Myfriends

近期评论