原题地址：http://www.rqnoj.cn/problem/273
题目大意：中文题不说了。
设从第i匹马到第j-1匹马放在一个马棚里得到的系数为f(i,j)。
状态表示：dp[i][j]表示前i匹马用j个分隔(j+1个马棚)分隔得到的最小的系数。则最后要求的就是dp[n][k-1]。
初始状态：dp[i][0]=f(0,i)
状态转移方程：
dp[i][j]=min{ dp[ii][j-1]+f(ii,i)，(j<=ii<i) }
即：要求dp[i][j]（前i匹马用j+1个马棚分隔得到的最小的系数），假设最后的1个独自关一个马棚，会得到dp[i-1][j-1]；假设最后两个独自关一个马棚，会得到dp[i-2][j-1]+最后两匹马关一起的系数。。。在这些情况中，选择一个最小的作为dp[i][j]的值。
解题代码：
1 #include<stdio.h> 2 #include<iostream> 3 using namespace std; 4 int dp[505][505]; 5 int a[505]; 6 int ans[505][505]; 7 int main() 8 { 9 int n,k,i,j,ii; 10 scanf("%d%d",&n,&k); 11 for(i=0;i<n;i++) 12 { 13 scanf("%d",&a[i]); 14 } 15 for(i=0;i<n;i++) 16 { 17 int nn[2]={0,0}; 18 for(j=i+1;j<=n;j++) 19 { 20 nn[a[j-1]]++; 21 ans[i][j]=nn[0]*nn[1]; 22 } 23 } 24 for(i=1;i<=n;i++) 25 dp[i][0]=ans[0][i]; 26 for(j=1;j<k;j++) 27 { 28 for(i=j+1;i<=n;i++) 29 { 30 dp[i][j]=1<<30; 31 for(ii=j;ii<i;ii++) 32 { 33 int m=dp[ii][j-1]+ans[ii][i]; 34 dp[i][j]=dp[i][j]<m?dp[i][j]:m; 35 } 36 } 37 } 38 printf("%d\n",dp[n][k-1]); 39 return 0; 40 }
【解题报告】[动态规划] RQNOJ - PID273 / 马棚问题,布布扣,bubuko.com
【解题报告】[动态规划] RQNOJ - PID273 / 马棚问题
原文：http://www.cnblogs.com/syiml/p/3679331.html
