RQNOJ273 马棚问题

题目描述

每天，小明和他的马外出，然后他们一边跑一边玩耍。当他们结束的时候，必须带所有的马返回马棚，小明有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

样例输出

枚举分组区间进行转移。

 /*by SilverN*/

 //WA 1:j每次从0开始循环，T掉一个点

 //       改成从c-1开始循环以后，904ms卡过

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int w[mxn],b[mxn];

 int f[mxn][mxn];

 int n,k;

 int main(){

     memset(f,0x2f,sizeof f);

     int i,j;

     n=read();k=read();

     int x;

     for(i=;i<=n;i++){

         x=read();

         if(x)b[i]++;

         else w[i]++;

         b[i]+=b[i-];

         w[i]+=w[i-];

     }

     f[][]=;

     for(int c=;c<=k;++c){

         for(i=c;i<=n;++i){

             for(j=c-;j<i;++j){

                 f[i][c]=min(f[i][c],f[j][c-]+(b[i]-b[j])*(w[i]-w[j]));

             }

         }

     }

     printf("%d\n",f[n][k]);

     return ;

 }

巴特西

RQNOJ273 马棚问题

最新文章

热门文章