本文主要是介绍rqnoj-273-马棚问题-dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
dp[i][j]: 从0到i匹马，住进j个马棚里，最小的不愉快系数。
num[i][j]: 把第i匹马到第j匹马放进一个马棚里，产生的不愉快系数
dp[i][j]=min(dp[i][j],dp[ii][j-1]+num[ii+1][i]);
时间复杂度：n*n*k
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
#define INF 999999
#define maxn 550
int ns[2][maxn];
int dp[maxn][maxn];
int a[maxn];
int num[maxn][maxn];
int ii;
int main()
{int n,k,i,j;while(~scanf("%d%d",&n,&k)){for(i=0;i<n;i++){scanf("%d",&a[i]);ns[0][i+1]=ns[0][i];ns[1][i+1]=ns[1][i];ns[a[i]][i+1]++;}for(i=0;i<n;i++){for(j=0;j<n;j++){dp[i][j]=INF;}}for(i=0;i<n;i++){for(j=0;j<i;j++){num[j][i]=(ns[0][i+1]-ns[0][j])*(ns[1][i+1]-ns[1][j]);}}for(i=0;i<n;i++)dp[i][1]=num[0][i];for(i=0;i<n;i++){for(j=2;j<=k;j++){for(ii=0;ii<i;ii++){dp[i][j]=min(dp[i][j],dp[ii][j-1]+num[ii+1][i]);}}}cout<<dp[n-1][k]<<endl;}return 0;
}
这篇关于rqnoj-273-马棚问题-dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
