# Gori#022(AGC001&EDPC)
# A - BBQ Easy
# 概要
長さがの串が本ある.
この時, 本の串をペアにして, 短い方の串の長さだけ具材を刺せる.
上手く串でペアを作った時の, 刺せる具材の最大値を求めよ.
# 解法
直感的にわかると思うが, 最適なペアの作り方は本の串の差の絶対値が最小の時である.
したがって, をソートしておき, 先頭から順番に串刺しにしていき, その最大値を求めれば良い.
#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までたどり着こうとしている.
- 足場にいる時, 足場もしくは足場にジャンプする
- ジャンプした先の足場をとすると, のコストを支払う
このとき, カエルが足場にたどり着くまでに支払うコストの総和の最小値を求めよ.
# 解法
以前解いた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;
}
以上.
お疲れ様でした.