0106-Discounts of Buckwheat
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0106
全探索でも余裕があるはず。
int minv[51]; void slove(){ for(int i=0;i<26;i++){ for(int j=0;j<18;j++){ for(int k=0;k<11;k++){ if(i*2+j*3+k*5<51){ minv[i*2+j*3+k*5]=min(minv[i*2+j*3+k*5],(i/5)*1520+(i%5)*380+(j/4)*1870+(j%4)*550+(k/3)*2244+(k%3)*850); } } } } } int main(int argc,char *argv[]){ for(int i=0;i<51;i++) minv[i]=999999; slove(); int w;while(1){ scanf("%d",&w);if(w==0) return 0; w/=100; printf("%d\n",minv[w]); } return 0; }