Bookshelf題解動态規劃DP

 Description       
         

Robby bought a new bookshelf, and he wanted to put all his N books on it. The bookshelf contains K layers, 
and the heights of each layer are variable. That is, the minimum height of one layer is equal to the maximum 
height of all the books in this layer. And the height of the bookshelf is the sum of all layers' heights.
Now Robby wants to make the height of his bookshelf as low as possible, but he don't want to break the order 
of the books, that is, each layer must contain the consecutive books of the original book series. And each 
layer must contain at least one book.

        
 Input       
         

There are several test cases in the input. 
The first line of each test case contains two integers N and K (1 ≤ K ≤ N ≤ 100). 
The second line contains N integers, indicating the heights of the books. You can assume 
the height of every book is no more than 1000.

The input is terminated with N = K = 0. 

        
 Output       
         

Output one line for each test case, that is, the minimum height of the bookshelf.

        
 Sample Input       
         

4 2
1 4 2 3
4 2
4 1 2 3
4 4
1 2 3 4
0 0

        
 Sample Output       
         

5
7
10

        
 Hint       
         

For the first sample, the best strategy is 1+max(4,2,3)=5
For the second sample, the best strategy is max(4,1,2)+3=7
For the third sample, the best strategy is 1+2+3+4=10

        
 Source       
         

TJU Programming Contest 2007 by RoBa
      

有序的劃分模型      

關鍵是要确定第i本書要放到那層書架上。      

另dp[i][j]為第i本書放到第j層書架上時的總高度的最小值。
則dp[n][k]即為所求。
dp[i][0]=INF      

對于第i本書，能放到的書架層數x是有個範圍的。
對于第x層書架，能放進去的書也是有個範圍的。      

dp[i][j]=min{dp[k-1][j-1]+M[k][i],k>=j&&k<=i} 
①單獨放到j層書架上。
②第k本書到第i本書放到第j層書架上。
取最小值
其中M[k][i]需要預處理出來第k本書到第i本書之間（包含）的最大書本高度。      

是以算法複雜度為O(n^3).      

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,a[105],mm[105][105],dp[105][105];
int main()
{
    while(scanf("%d%d",&n,&m),n+m)
    {
        int i,j,k;
        for(i=1;i<=n;i++)
            scanf("%d",a+i);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            mm[i][i]=a[i];
            dp[i][0]=999999999;
            for(j=i+1;j<=n;j++)
            {
                mm[i][j]=mm[i][j-1];
                if(a[j]>mm[i][j-1])
                    mm[i][j]=a[j];
            }
        }
        for(i=1;i<=n;i++)
            for(j=max(1,m+i-n);j<=i;j++)
            {
                int t=999999999;
                for(k=j;k<=i;k++)
                    if(dp[k-1][j-1]+mm[k][i]<t)
                        t=dp[k-1][j-1]+mm[k][i];
                dp[i][j]=t;    
            }
        printf("%d/n",dp[n][m]);    
    }
}