# Gori#022(AGC001&EDPC)

# A - BBQ Easy

# 概要

長さが $L_i$ の串が $2 \times N$ 本ある.
この時, $2$ 本の串をペアにして, 短い方の串の長さだけ具材を刺せる.
上手く串でペアを作った時の, 刺せる具材の最大値を求めよ.

# 解法

直感的にわかると思うが, 最適なペアの作り方は $2$ 本の串の差の絶対値が最小の時である.
したがって, $L_i$ をソートしておき, 先頭から順番に串刺しにしていき, その最大値を求めれば良い.

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

int main() {
  int n; cin >> n;
  vector<int> l(2*n);
  for(int i=0;i<2*n;++i)cin >>l[i];
  sort(l.begin(), l.end());
  int ans =0;
  for(int i=1;i<2*n; i+=2){
    int len = min(l[i], l[i-1]);
    ans += len;
  }
  cout << ans << endl;
  return 0;
}

# B - Mysterious Light

スライドを作ったので, そちらを参照ください.
AGC001-B Mysterious Light 考察と実装 (opens new window)

# A - Frog1

# 概要

$1$ から $N$ までの番号が振られている $N$ 個の足場がある.
足場1にいるカエルは, 以下の行動を繰り返して, 足場Nまでたどり着こうとしている.

足場 $i$ にいる時, 足場 $i+1$ もしくは足場 $i+2$ にジャンプする
ジャンプした先の足場を $j$ とすると, $|h_i - h_j|$ のコストを支払う

このとき, カエルが足場 $N$ にたどり着くまでに支払うコストの総和の最小値を求めよ.

# 解法

以前解いたC - 柱柱柱柱柱と同様にして解ける.

状態の持ち方

dp[i] := i番目の足場にいるときの合計コストの最小値

遷移の仕方カエルは, ある足場から1個もしくは2個右にある足場のどちらかに移動することが可能で, コストは現在いる足場との高さの差の絶対値である.
したがって, 遷移は以下のようにかける.

if (i>0) dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]));
if (i>1) dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]));

以上をまとめてDPを用いれば良い.

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

int main() {
  int n; cin >> n;
  vector< int > h(n);
  for(int i=0;i<n;++i) cin >> h[i];

  vector< int > dp(n+1, 1e9+1);

  dp[0] = 0;
  for(int i=0;i<n;++i){
    if (i>0) dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]));
    if (i>1) dp[i] = min(dp[i], dp[i-2] + abs(h[i] - h[i-2]));
  }
  cout << dp[n-1] << endl;

  return 0;
}

以上.
お疲れ様でした.

# Gori#022(AGC001&EDPC)

# A - BBQ Easy

# 概要

# 解法

# B - Mysterious Light

# A - Frog1

# 概要

# 解法

# 参考資料