[JOI精進録] 難易度6「オレンジの出荷」(第15回日本情報オリンピック 本選A)

これ、だいぶ正しいんだけど、キャベツを厳密にAtCoderが管理しているわけではないから、「大半のキャベツは自分で勝手に畑から飛んで行って出荷されていく」ってのがAtCoderが儲けるのが難しい原因なのよねｗhttps://t.co/B7xM4FQQ5O

— chokudai(高橋 直大)@AtCoder社長 (@chokudai) December 1, 2020

キャベツだったら多分笑い転げてた。2016年の問題なのでキャベツとは全く関係ない。

問題リンク

atcoder.jp

問題概要

オレンジを全ていくつかの箱に詰め込む。箱に詰め込まれるオレンジは連続していなければならない。
costは箱の固定コスト、詰め込む個数、詰め込むオレンジの最大値と最小値でと表される。
costの総和の最小値を求めなさい。

解説

AC解法 (100/100点)

個前のオレンジまで詰め込んだときのcostの総和の最小値
としてRMQを使ってを更新していく。
高速に更新するためにmodとか使ってるので詳しい説明は後になってはもうできない。だがACしているのでﾖｼ｡

ACコード

#include <bits/stdc++.h>
using namespace std;

int main(){
#define int long long
  int n,m,k; cin >> n >> m >> k;
  vector<int> A(n),dp(m+1,0); for (int& a:A) cin >> a;
  vector<int> rminq(m+1),rmaxq = rminq; fill(rminq.begin()+1,rminq.end(),A[0]),fill(rmaxq.begin()+1,rmaxq.end(),A[0]);
  // dp[i] = i個前まで詰めたときの最小値
  dp[0] = k;
  for (int i(1);i < n;++i){
    for (int j(m);j > 1;--j) rminq[j] = min(rminq[j-1],A[i]),rmaxq[j] = max(rmaxq[j-1],A[i]);
    rminq[1] = A[i],rmaxq[1] = A[i];
    int b = -i; b%=m+1; while (b<0) b = m+1+b;
    dp[b] = dp[(b+1)%(m+1)]+k;
    for (int j(0);j <= min(m-1,i);++j){
      int c = b+j+1; c%=m+1;
      dp[b]=min(dp[b],(j==i?0:dp[c])+k+(j+1)*(rmaxq[j+1]-rminq[j+1]));
    }
    if (i<m&&dp[i]==0) dp[i] = k;
  }
  int b = -(n-1); b%=m+1; while (b<0) b = m+1+b;
  cout << dp[b] << endl;
}

提出結果

atcoder.jp