整理圖書

時間限制：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

第二組樣例:只有一本書，無需裝訂

解題思路：這道題最開始作死。。。自己yy了一個狀態dp[i][j]表示前i個序列裝訂了j次最大高度的最小值，那么這里需要3層for循環，加上一些剪枝。。然后超時。。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 1005; const int inf = 0x3f3f3f3f; int n,a[maxn],sum[maxn]; int dp[maxn][maxn];int main() {int cas = 1,i,j,k;while(scanf("%d",&n)!=EOF){for(i = 1; i <= n; i++){scanf("%d",&a[i]);sum[i] = sum[i-1] + a[i];}memset(dp,inf,sizeof(dp));dp[0][0] = 0;dp[1][0] = a[1];for(i = 2; i <= n; i++)for(j = 0; j < i; j++){for(k = 0; k <= j; k++){if(sum[i] - sum[i-k-1] >= dp[i-k-1][j-k]){dp[i][j] = sum[i] - sum[i-k-1];break;}}if(k <= j) break;}for(int i = 0; i < n; i++)if(dp[n][i] != inf){printf("Case %d: %d\n",cas++,i);break;}}return 0; }
其實這里不需要這么麻煩，直接dp[i]表示前i個序列的最小整理次數，那么我們只需要維護一個當前的最大高度h即可，因為這個h一定是最后一次裝訂時可以確定的，那么直接維護h即可找到最小的裝訂次數。比我之前那個狀態又優化了很多。

#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 5050; int a[maxn], sum[maxn], dp[maxn], h[maxn]; int main() {int n, cnt = 0;while ( scanf ( "%d", &n ) != EOF ) {memset ( sum, 0, sizeof ( sum ) );for ( int i = 1; i <= n; i++ ) {scanf ( "%d", &a[i] );h[i] = max ( h[i - 1], a[i] );sum[i] = sum[i - 1] + a[i];}memset ( dp, INF, sizeof ( dp ) );dp[0] = 0; //當前0或1摞書非降序時需要最少裝訂次數為0dp[1] = 0;for ( int i = 2; i <= n; i++ ) {for ( int j = i - 1; j >= 0; j-- ) {if ( h[j] <= sum[i] - sum[j] ) {//當前j個中最大高度大于等于從j到i的總書高，進行狀態轉移if ( dp[i] > dp[j] + i - j - 1 ) {dp[i] = dp[j] + i - j - 1; //更新dph[i] = sum[i] - sum[j]; //更新前i摞書中最高的書高高度break;}}}}printf ("*Case %d: %d\n",++cnt, dp[n] );}return 0; }

總結

以上是生活随笔為你收集整理的nyoj 1216 整理图书(dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。