双色马制作者：谭智超培训课件.ppt

双色马制作者：谭智超 动态dp类型题目 水平有点不够，目前代码能力很弱啊尽力了。 * 题目大意： 要把所有的马排成一条直线回去，尽量让马少移动，把前p1匹马放在第一个地方，下面p2匹马放在第二个地方等等，而且，他不想k个地方任何一个是空的，并且没有马留在外面。 有黑白两种颜色的马，两种颜色的马相处不好，如果有i匹黑马和j匹白马同在一个地方那么这个地方的忧愁数为i*j，总忧愁数是所有地方忧愁数的和。 求得结果：找到一种方法把n匹马放进k个地方使忧愁数最小。 * 大体思路： 区间类动态dp 只需关注最后一个 地方该分配多少匹马就可以啦！ 采取部分和的思想例如用是s【i】表示前i匹马中有多少匹白 马。则是s【i】-s【j】（ji）表示j至i这个区间中有多少匹白马。 设f【i】【j】为第i个地方分配j匹马的忧愁最小值，则动态转移方程为： f【i】【j】=min{f【i-1】【k】+（s【j】-s【k】）*（j-k-（s【j】-s【k】）），f【i】【j】}//请好好理解这个方程； 即到第i个地方分配j匹马的忧愁最小值等于前i-1个地方分配k匹马的最小忧愁加上（j-k）匹马的忧愁值。 * 大体代码如下： for(i=1; i=n; i++) cina[i]; for (i=1; i=n; i++) { if (a[i]==1) s[i]=s[i-1]+1;//这一段不解释； else s[i]=s[i-1]; } * for (j=1; j=k; j++) for (i=1; i=n; i++) { min=999999999;//求最小的就先赋值最大 for (d=0; di; d++) if (minf[d][j-1]+(s[i]-s[d]*(i-d-(s[i]-s[d])))//求每一个最小的忧愁值 { min=f[d][j-1]+(s[i]-s[d])*(i-d-(s[i]-s[d]));//转移 f[i][j]=min;//现在第i个地方就是最少的忧愁值 } } coutmin;//输出忧愁值。 * 谢谢大家 如有水平不足之处请各位指正， 如又看不懂的地方QQ私聊本人：3110034801； 第一次出PPt 有点疯。 出产包售，不懂就问。 * 精品文档