首页 > 代码库 > URAL 1167. Bicolored Horses (DP)
URAL 1167. Bicolored Horses (DP)
题目链接
题意 :农夫每天都会放马出去,然后晚上把马赶入马厩,于是让马排成一行入马厩,但是不想马走更多的路,所以让前p1匹入第一个马厩,p2匹马入第二个马厩…………但是他不想让他的任何一个马厩空着,所有的马都必须入马厩。有两种颜色的马,如果 i 匹黑马与 j 匹白马同在一个马厩,不愉快系数是 i * j,总系数就是k个系数相加。让总系数最小。
思路 : dp[i][j] 代表的是前 i 个马厩放 j 匹马的最小不愉快系数值。
1 //1167 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 6 using namespace std ; 7 8 int dp[510][510],black[510],white[510] ; 9 10 void Init()11 {12 for(int i = 0 ; i < 510 ; i++)13 {14 for(int j = 0 ; j < 510 ; j++)15 dp[i][j] = 99999999 ;16 dp[i][i] = 0 ;17 }18 memset(black,0,sizeof(black)) ;19 memset(white,0,sizeof(white)) ;20 }21 int main()22 {23 int N,K,x ;24 while(~scanf("%d %d",&N,&K))25 {26 Init() ;27 for(int i = 1 ; i <= N ; i++)28 {29 scanf("%d",&x) ;30 black[i] = black[i-1] + x ;31 white[i] = white[i-1] + (1-x) ;32 }33 for(int i = 1 ; i <= K ; i++)34 {35 for(int j = i ; j <= N-(K-i) ; j ++)36 {37 for(int k = i-1 ; k < j ; k++)38 {39 dp[i][j] = min(dp[i-1][k] + (black[j]-black[k])*(white[j]-white[k]) ,dp[i][j]);40 }41 }42 }43 printf("%d\n",dp[K][N]) ;44 }45 return 0 ;46 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。