首页 > 代码库 > rqnoj 马棚问题
rqnoj 马棚问题
题目描述
每天,小明和他的马外出,然后他们一边跑一边玩耍。当他们结束的时候,必须带所有的马返回马棚,小明有K个马棚。他把他的马排成一排然后跟随它走向马棚,因为他们非常疲劳,小明不想让他的马做过多的移动。因此他想了一个办法:将马按照顺序放在马棚中,后面的马放的马棚的序号不会大于前面的马放的马棚的序号。而且,他不想他的K个马棚中任何一个空置,也不想任何一匹马在外面。已知共有黑、白两种马,而且它们相处得并不十分融洽。如果有i个白马和j个黑马在一个马棚中,那么这个马棚的不愉快系数将是i*j。所有k个马棚不愉快系数的和就是系数总和。确定一种方法把n匹马放入k个马棚,使得系数总和最小。
输入格式
输入:在第一行有两个数字:n(1≤n≤500)和k(1≤k≤n)。在接下来的n行是n个数。在这些行中的第i行代表队列中的第i匹马的颜色:1意味着马是黑色的,0意味着马是白色的。
输出格式
输出:只输出一个单一的数字,代表系数总和可能达到的最小值。
样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
拥有 RQNOJ 账号,您可以:
- 查看海量题库,并提交您的代码
- 参加比赛,证明实力
- 与大家讨论,解答疑问,分享心得
相关讨论
/*前J匹马放进i个马棚。 f[i][j]=min(f[i-1][k]+s[k+1][j],f[i][j])*/#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<string>#include<algorithm>using namespace std;int n,m,f[510][510],s[510][510],a[510];int main(){ scanf("%d%d",&n,&m); memset(f,0x3f,sizeof(f)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int x=0; for(int k=i;k<=j;k++) x=x+a[k]; s[i][j]=(j-i+1-x)*x; } f[1][i]=s[1][i]; } for(int i=2;i<=m;i++) for(int j=1;j<=n;j++) for(int k=i-1;k<=j;k++) f[i][j]=min(f[i][j],f[i-1][k]+s[k+1][j]); printf("%d\n",f[m][n]); return 0;}
rqnoj 马棚问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。