# Gori#022(AGC001&EDPC)

# A - BBQ Easy

# 概要

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

# 解法

直感的にわかると思うが, 最適なペアの作り方は22本の串の差の絶対値が最小の時である.
したがって, LiL_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 考察と実装

# A - Frog1

# 概要

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

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

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

# 解法

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

  1. 状態の持ち方
dp[i] := i番目の足場にいるときの合計コストの最小値
  1. 遷移の仕方 カエルは, ある足場から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;
}

以上.
お疲れ様でした.

# 参考資料

Last Updated: 2019-2-15 04:38:05