整理圖書


整理圖書


時間限制:3000 ms  |  內存限制:65535 KB


難度:5



描述



小明是圖書鸛貍猿,他有很多很多的書堆在瞭一起擺在瞭架子上,每摞書是橫著放的,而且每摞書是訂好的


是一個整體,不可分開,(可以想象架子是一條直線),但是這些書高度卻參差不齊,小明有強迫癥,看不得不整齊


所以他想讓這些書的高度形成一個非降序列他才舒心,可是這些書是有序的,所以他隻能把其中的一摞書和他相鄰的書裝訂在一起


形成一摞新的書,那麼他最少的裝訂次數是多少呢



輸入

多組測試數據,處理到文件結束

每組數據開始有一個n(1<=n<=1000)表示有n摞書

接下來一行是這n摞書的高度a[i],(1<=a<=10^5)(雖然這個高度有點扯淡)

輸出

首先輸出Case num : 表示第幾組數據

接下來對於每組數據輸出最少的裝訂次數

樣例輸入


5
8 2 7 3 1
1
100


樣例輸出


Case 1: 3
Case 2: 0


提示

第一組樣例:將後4本書裝訂在一起,共裝訂3次,組成8 13

第二組樣例:隻有一本書,無需裝訂

解題思路:我們定義dp[i]表示將前i摞圖書整理成非降序列時的最少步數。定義h[i]表示前i摞書的最高的書高。同時sum[i]來記錄前i摞書的總高度。dp[i]=dp[j]+(i-j-1)。如果前j摞書中最高書高小於等於sum[i]-sum[j]。則判斷是否將j--->i這麼多摞書合並在一塊兒是否比dp[i]更小,如果是,則更新dp[i],h[i]。為什麼從i-1開始隻要能找到更新dp[i]的就算是最優結果瞭?因為dp[j]已經是最優結果瞭,那麼我在最優解的基礎上找到最小的增量,那麼dp[i]也肯定是最優解瞭


#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
int main()
{
const int maxn=1005;
int n,cnt=0;
while(scanf("%d",&n)!=EOF)
{
int high[maxn],sum[maxn],hmax[maxn];
sum[0]=0,hmax[0]=0;
for(int i=1; i<=n; i++)
{
cin>>high[i];
sum[i]=sum[i-1]+high[i];
hmax[i]=max(high[i],hmax[i-1]);
}
int dp[maxn];
for(int i=0; i<maxn; i++)
dp[i]=1e6;
dp[0]=dp[1]=0;
for(int i=2; i<=n; i++)
for(int j=i-1; j>=0; j--)
if(hmax[j]<=sum[i]-sum[j]&&dp[i]>dp[j]+i-j-1)//當前j個中最大高度大於等於從j到i的總書高,進行狀態轉移
{
dp[i]=dp[j]+i-j-1;//更新dp
hmax[i]=sum[i]-sum[j];////更新前i摞書中最高的書高高度
break;
}
cnt++;
cout<<"Case "<<cnt<<": "<<dp[n]<<endl;
}
return 0;
}




0 個評論

要回覆文章請先登錄註冊