c779 - 106北二4.盆栽展覽
題目描述
題目給定一排盆栽的高度，以及相鄰盆栽的最大高度差。要求計算擺放這些盆栽所需的最低展示架總高度。展示架的高度可以調整，但相鄰盆栽的高度差不能超過給定的限制。
解題思路
本題可以使用動態規劃來解決。dp[i][j] 表示擺放前 i 個盆栽，且第 i 個盆栽高度為 j 時，所需的最低展示架總高度。
初始化 dp[0][j]，表示擺放第一個盆栽時的最小高度。如果 j 小於第一個盆栽的高度，則設為無限大；否則，設為 j 減去第一個盆栽的高度。
對於後續的盆栽，我們遍歷所有可能的高度 j，並考慮前一個盆栽的高度 k。如果 j 和 k 的高度差不超過限制，則更新 dp[i][j] 的值。
最後，遍歷所有可能的高度 j，找到 dp[n-1][j] 的最小值，即為所需的最低展示架總高度。
複雜度分析
- 時間複雜度: O(n * m^2)，其中 n 是盆栽的數量，m 是盆栽的最大高度。
- 空間複雜度: O(n * m)，其中 n 是盆栽的數量，m 是盆栽的最大高度。
程式碼
#include <iostream>
#include <climits>
using namespace std;
long long a[35],dp[35][2005],n,c,ans=INT_MAX;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> a[n])++n;
n--;
c=a[n];
for(int i=0;i<a[0];++i)
dp[0][i]=INT_MAX;
for(int i=a[0];i<=2000;++i)
dp[0][i]=i-a[0];
for(int i=1;i<n;++i){
for(int j=0;j<=2000;++j)
dp[i][j]=INT_MAX;
for(int j=a[i],it=a[i]-c,it2=a[i]+c;j<=2000;++j,++it,++it2)
for(int k=max(it,0);k<=min(it2,2000);++k)
dp[i][j]=min(dp[i][j],dp[i-1][k]+j-a[i]);
}
for(int i=0;i<=2000;++i)
ans=min(dp[n-1][i],ans);
cout << ans;
}