c779. 106北二4.盆栽展覽

題目 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