第7回日本情報オリンピック 本選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#D - ぴょんぴょん川渡り
https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=8
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #D - ぴょんぴょん川渡り https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=8 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; void replace_min(ll& n,ll m){ if(n>m){ n=m; } } int main(void){ ll n,m; cin>>n>>m; vector<ll> k(n); vector<vector<ll>> z(n),d(n); for(ll i=0;i<n;i++){ cin>>k[i]; z[i].resize(k[i]); d[i].resize(k[i]); for(ll j=0;j<k[i];j++){ cin>>z[i][j]>>d[i][j]; } } vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(10,vector<ll>(m+1,1000000000))); for(ll i=0;i<k[0];i++){ dp[0][i][0]=0; } for(ll i=0;i<k[1];i++){ dp[1][i][1]=0; } for(ll i=0;i<n-1;i++){ for(ll x=0;x<k[i];x++){ for(ll y=0;y<k[i+1];y++){ for(ll j=0;j<=m;j++){ replace_min(dp[i+1][y][j],dp[i][x][j]+(d[i][x]+d[i+1][y])*abs(z[i][x]-z[i+1][y])); } } } if(i==n-2){ continue; } for(ll x=0;x<k[i];x++){ for(ll y=0;y<k[i+2];y++){ for(ll j=0;j<m;j++){ replace_min(dp[i+2][y][j+1],dp[i][x][j]+(d[i][x]+d[i+2][y])*abs(z[i][x]-z[i+2][y])); } } } } ll ans=1000000000; for(ll i=0;i<k[n-2];i++){ for(ll j=0;j<m;j++){ replace_min(ans,dp[n-2][i][j]); } } for(ll i=0;i<k[n-1];i++){ for(ll j=0;j<=m;j++){ replace_min(ans,dp[n-1][i][j]); } } cout<<ans<<endl; return 0; }