【解题报告】[动态规划] RQNOJ

原题地址：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]的值。

解题代码：

 #include<stdio.h>

 #include<iostream>

 using namespace std;

 int dp[][];

 int a[];

 int ans[][];

 int main()

 {

     int n,k,i,j,ii;

     scanf("%d%d",&n,&k);

     for(i=;i<n;i++)

     {

         scanf("%d",&a[i]);

     }

     for(i=;i<n;i++)

     {

         int nn[]={,};

         for(j=i+;j<=n;j++)

         {

             nn[a[j-]]++;

             ans[i][j]=nn[]*nn[];

         }

     }

     for(i=;i<=n;i++)

         dp[i][]=ans[][i];

     for(j=;j<k;j++)

     {

         for(i=j+;i<=n;i++)

         {

             dp[i][j]=<<;

             for(ii=j;ii<i;ii++)

             {

                 int m=dp[ii][j-]+ans[ii][i];

                 dp[i][j]=dp[i][j]<m?dp[i][j]:m;

             }

         }

     }

     printf("%d\n",dp[n][k-]);

     return ;

 }

巴特西

【解题报告】[动态规划] RQNOJ - PID273 / 马棚问题

最新文章

热门文章