本文共 871 字，大约阅读时间需要 2 分钟。

题目大意：

      有n堆石子，每次可以选择连续的一段合并，最少l个，最多r个，每次合并的花费为这些堆的石子的和，问最小花费是多少

题解：

     训练的时候反映出来了这是区间dp，并且是经典问题石子合并的延伸  

    但是自己犯了一个非常愚蠢的错误，很随意地想了想n的范围是100，竟然就觉得肯定是3重循环，而不能是4重，为什么不能是4重呢！！！

   

   dp[i][j][k]表示把区间[i,j]分成k堆的最小代价     

并且，把k分为k-1和1来计算

k=1时：

      dp[i][j][1] = min(dp[i][p][x-1]+dp[p+1][j][1]+sum[i][j] (i<=p<=j-1；L<=x<=R) )

k>1时：

     dp[i][j][k] = min(dp[i][p][k-1]+dp[p+1][j][1] ( i<=p<=j-1) )

还有很多细节需要处理，每一层枚举的上界下界可能都是问题

 

     新的区间dp类型，4重循环，开三维

    也由此明白了自己对dp的理解还远远不够.....

#include 
   
    #include 
    
     #include
     
      using namespace std;#define ll long long#define INF 0x3f3f3f3fint dp[200][200][200];int a[200];int sum[200];int main(){    //dp[i][j][k]把区间[i,j]分成k堆的最小代价    int n,l,r;    while(cin>>n>>l>>r)    {        memset(dp,INF,sizeof(dp));        for(int i=1; i<=n; ++i)        {            cin>>a[i];            sum[i]=sum[i-1]+a[i];            dp[i][i][1]=0;        }        for(int len=1; len
     
    
   

转载地址：http://jyfgf.baihongyu.com/