首页 > 代码库 > 马棚问题
马棚问题
马棚问题
Time Limit: 2 Sec Memory Limit: 64 MBSubmit: 292 Solved: 74
Description
每天，小明和他的马外出，然后他们一边跑一边玩耍。当他们结束的时候，必须带所有的马返回马棚，小明有K个马棚。他把他的马排成一排然后跟随他走向马棚。因为他们非常疲倦，小明不想让他的马做过多的移动。因此他想了一个办法：将马按照顺序放在马棚中，后面的马放的马棚的序号不会大于前面的马放的马棚的序号。而且他不想让他的K个马棚中任何一个空着，也不想让任何一匹马在外面。已知有黑白两种马，而且它们相处的很不融洽。如果有i个白马和j个黑马在一个马棚中，那么这个马棚的不愉快系数是i*j。所有k个马棚不愉快系数的和就是系数总和。确定一种方法把n匹马放入k个马棚，使得系数总和最小。
Input
多个测试组，每组测试第一行有2个数字：n( 1 <= n <= 500)和k( 1 <= k <= n). 接下来的n行是n个数，在这些行中的第i行代表队列中的第i匹马的颜色：1意味着马是黑色的，0则是白色的。处理到结束。
Output
对每组测试数据输出一行，只输出一个数字，代表系数总和可能达到的最小值
Sample Input
6 3110101
第一次独立完成的并AC了的dp,第一次没AC,就把no.1定义的全局变量放到main里，结果竟然通过了，这真心有点无语。no.2是AC版。no.1:
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #define INF 1<<30 5 int horse,stable; 6 int color[600]; 7 int white[500],black[500]; 8 int dp[501][501]; 9 10 int min(int a,int b)11 {12 return a<b?a:b;13 }14 15 int main()16 {17 // freopen("a.txt","r",stdin);18 int i,j,k,tmp1,tmp2;19 20 while(scanf("%d%d",&horse,&stable)==2)21 {22 for(i=1;i<=horse;i++)23 {24 scanf("%d",&color[i]);25 }26 for(i=0;i<=horse;i++)27 for(j=0;j<=stable;j++)28 {29 dp[i][j]=INF;30 }31 memset(white,0,sizeof(white));32 memset(black,0,sizeof(black));33 for(i=1,j=1;i<=horse;i++,j++)34 {35 if(color[i]==0)36 {37 white[j]+=white[j-1]+1;38 black[j]=black[j-1];39 }40 else41 {42 black[j]+=black[j-1]+1;43 white[j]=white[j-1];44 }45 dp[i][1]=white[j]*black[j];46 //printf("dp[%d][1]=%d\n",i,dp[i][1]);47 // printf("white[%d]=%d,black[%d]=%d\n",j,white[j],j,black[j]);48 }49 50 for(j=2;j<=stable;j++)51 for(i=j;i<=horse;i++)52 {53 for(k=j-1;k<i;k++)54 {55 tmp1=white[i]-white[k];56 tmp2=black[i]-black[k];57 dp[i][j]=min(dp[i][j],dp[k][j-1]+tmp1*tmp2);58 }59 // printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);60 }61 62 printf("%d\n",dp[horse][stable]);63 }64 return 0;65 }66
no.2:(感觉就是"数字游戏"的简化版)
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #define INF 1<<30 5 6 int min(int a,int b) 7 { 8 return a<b?a:b; 9 }10 11 int main()12 {13 // freopen("a.txt","r",stdin);14 int i,j,k,tmp1,tmp2;15 int horse,stable;16 int color[600];17 int white[500],black[500];18 int dp[501][501];19 while(scanf("%d%d",&horse,&stable)==2)20 {21 for(i=1;i<=horse;i++)22 {23 scanf("%d",&color[i]);24 }25 for(i=0;i<=horse;i++)26 for(j=0;j<=stable;j++)27 {28 dp[i][j]=INF;29 }30 memset(white,0,sizeof(white));31 memset(black,0,sizeof(black));32 for(i=1,j=1;i<=horse;i++,j++)33 {34 if(color[i]==0)35 {36 white[j]+=white[j-1]+1;37 black[j]=black[j-1];38 }39 else40 {41 black[j]+=black[j-1]+1;42 white[j]=white[j-1];43 }44 dp[i][1]=white[j]*black[j];45 //printf("dp[%d][1]=%d\n",i,dp[i][1]);46 // printf("white[%d]=%d,black[%d]=%d\n",j,white[j],j,black[j]);47 }48 49 for(j=2;j<=stable;j++)50 for(i=j;i<=horse;i++)51 {52 for(k=j-1;k<i;k++)53 {54 tmp1=white[i]-white[k];55 tmp2=black[i]-black[k];56 dp[i][j]=min(dp[i][j],dp[k][j-1]+tmp1*tmp2);57 }58 // printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);59 }60 61 printf("%d\n",dp[horse][stable]);62 }63 return 0;64 }65
马棚问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。