PKU 1651 Multiplication Puzzle
http://poj.org/problem?id=1651
n枚のカードが横に並べられている。
ここからn-2枚のカードを取り除くときに、取り除くカードとその両隣のカードに書かれた数字の積加算していく。
ここであたえられたカードの並びに対して、得られる得点の最小値はいくつかになるかを答えるというような問題。
メモ化再帰でやりました。
書き慣れていないせいか、かなりバグバグになりました。
bool vis[110][110]; int memo[110][110]; int in[110]; int rec(int l,int r){ if(vis[l][r]){ return memo[l][r]; } vis[l][r]=true; if(l>=r)return 0; if(l+1==r){ return memo[l][r]=in[l-1]*in[l]*in[l+1]; } int ret=100000000; for(int i=l;i<r;++i){ int a=rec(l,i); int b=rec(i+1,r); ret=min(ret,a+b+in[l-1]*in[i]*in[r]); } return memo[l][r]=ret; } main(){ int n; cin>>n; rep(i,n)cin>>in[i]; cout<<rec(1,n-1)<<endl; }