第9回日本情報オリンピック 本選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#B - お菓子の分割
https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf#page=5
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #B - お菓子の分割 https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf#page=5 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int main(void){ int n; cin>>n; vector<int> t(n,0); for(int i=0;i<n-1;i++){ cin>>t[i]; } vector<int> m1(20001,1000000000),m2(10001,10000000000); vector<vector<int>> dp(n/2+1,vector<int>(2,1000000000)); dp[0][0]=0; dp[0][1]=0; m1[10000]=0; m2[0]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=min(i,n/2);j++){ dp[j][0]=m1[j-i+10000]+t[i-1]; dp[j][1]=m2[j]+t[i-1]; m1[j-i+10000]=min(m1[j-i+10000],dp[j][1]); m2[j]=min(m2[j],dp[j][0]); } } cout<<min(dp[n/2][0],dp[n/2][1])<<endl; return 0; }