马棚问题

Time Limit: 2 Sec Memory Limit: 64 MB
Submit: 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 3
1
1
0
1
0
1

第一次独立完成的并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             else
41             {
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
",i,dp[i][1]);
47          //   printf("white[%d]=%d,black[%d]=%d
",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
",i,j,dp[i][j]);
60             }
61 
62         printf("%d
",dp[horse][stable]);
63     }
64     return 0;
65 }
66

View Code

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             else
40             {
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
",i,dp[i][1]);
46          //   printf("white[%d]=%d,black[%d]=%d
",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
",i,j,dp[i][j]);
59             }
60 
61         printf("%d
",dp[horse][stable]);
62     }
63     return 0;
64 }
65

View Code