題目 Problem#
題目連結：https://zerojudge.tw/ShowProblem?problemid=c779
敘述 Description#
盆栽協會為了推廣盆栽藝術將舉辦盆栽比賽與展覽。在展覽時，將依照比賽編號來依序擺放盆栽，但由於參賽盆栽的高度不一，為了方便評審評分與來賓觀賞，盆栽協會將訂做展示架來擺放盆栽，以便讓相鄰盆栽的高度差異不超過最大高度差。為了節省訂做成本，盆栽協會希望訂做的展示架高度越低越好。請你寫一個程式，根據相鄰最大高度差與每個盆栽的高度，計算擺放這排盆栽所需的最低展示架總高度。
舉例說明，以下例子中，第一列共有五個盆栽的高度。若相鄰最大高度差為 $5$，則第二列為每個盆栽的最低展示架高度,所以總高度為$0+118+153+0+282=553$。若相鄰最大高度差為 $50$，則第三列為每個盆栽的最低展示架高度，所以總高度為 $0+67+108+0+237=412$。
| 盆栽高度 | 401 | 284 | 254 | 412 | 125 |
|---|---|---|---|---|---|
| 相鄰最大高度差為 5 | 0 | 118 | 153 | 0 | 282 |
| 相鄰最大高度差為 50 | 0 | 67 | 108 | 0 | 237 |
輸入 Input#
測試資料有兩行。 第一行有 $A (1 \leq A \leq 30)$ 個以一個空格(white space)隔開的整數 $B (1 \leq B \leq 2000)$ 代表盆栽高度。 第二行有一個整數 $C (1 \leq C \leq 2000)$，代表相鄰最大高度差。
輸出 Output#
請輸出 1 個整數，代表擺放這排盆栽所需的最低展示架總高度。
範例輸入 Sample Input#
範例輸入一：
401 284 254 412 125
50
範例輸入二：
1010 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
5
範例輸出 Sample Output#
範例輸出一：
412
範例輸出二：
5
提示 Hint#
題解 Solution#
每個數字兩個之間有沒有差距超過相鄰最大高度差
我過程至少 $A$ 次，第一次可能還沒有跟上最高高度
程式碼 Accepted Code#
/*
Author: Jerry Yang C.H. (tico88612)
Date: 2020/4/9
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double,double> pdd;
#define SQ(i) ((i)*(i))
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) int(i.size())
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define X first
#define Y second
#ifdef tmd
#define debug(...) do{\
fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
_do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
_s<<"{";
for(It _it=_ita;_it!=_itb;_it++)
{
_s<<(_it==_ita?"":",")<<*_it;
}
_s<<"}";
return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,deque<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif
const ll MOD = 1000000007LL;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const int iNF = 0x3f3f3f3f;
// const ll MAXN =
/********** Good Luck :) **********/
int main()
{
IOS();
ll enter[35] = {0}, t = 0;
while(cin >> enter[t++]);
t--;
ll c = enter[--t];
ll ans = 0;
REP(i, t){
REP(j, t){
if (j == 0 && j != t - 1) {
if (j + 1 < t && enter[j] < enter[j + 1] - c){
ans += enter[j + 1] - c - enter[j];
enter[j] = enter[j + 1] - c;
}
} else if (j == t - 1) {
if (enter[j] < enter[j - 1] - c) {
ans += enter[j - 1] - c - enter[j];
enter[j] = enter[j - 1] - c;
}
} else {
int tt = max(enter[j - 1], enter[j + 1]);
if(tt - c > enter[j]){
ans += tt - c - enter[j];
enter[j] = tt - c;
}
}
}
}
cout << ans << '\n';
return 0;
}
後記 Afterword#
我發現外層迴圈設定 $2$ 次，還是可以 AC
根本證明這測資根本太水了
輸入
10 10 10 10 10 10 10 10 100 100
10
輸出
設定兩次：150
正確：360