問題
http://topcoder.bgcoder.com/print.php?id=209
複数の電力源が与えられて、エネルギーの値があらかじめわかっている。
隣り合う２つの電力源について、左側が入力値、右側が出力値をあらわす。
このとき、隣り合う２つの電力源を融合することができる。
融合するのに必要なコストは
左側の電力源をinpA、右側の電力源をconnection、その右側の電力源をoutBとすると、
cost=(inpA+sizeA)*connection*(outB+sizeB)
で表わされる。
sizeは最初は全て１であり、融合するとsizeA+sizeBが新しいサイズになる。
このとき、全ての電力源を融合するために必要な最小のコストを求める。
解き方
電力源の数は５０個なので、全探索しようとすると50!で間に合わない。
そのためｄｐを利用する。
まず、距離がlenにある電力源aとbをつなげるときの最小のコストを考える。
このときの最小のコストは、aとbを全ての場所で区切ったときのコストのうち最小、
つまりaとbの間で1~len-1で区切ったときのコストのうち最小のものになる。
上記について、lenを1からnまでの長さについて求めてあげれば
最終的に0からn-1までの最小のコストが求められる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[51][51];
class Assemble {
public: int minCost(vector<int> connect) {
int n=connect.size();
FORE(i,0,n+1)FORE(j,0,51)dp[i][j]=1e+9;
FORE(i,0,n+1)dp[i][i]=0;
FORE(len,2,n){
for(int i=0;i+len-1<=n-2;i++){
for(int j=i+1;j<=i+len-1;j++){
int sizea=j-i;
int sizeb=(i+len-1)-j+1;
int cost=(connect[i]+sizea)*connect[j]*(connect[i+len]+sizeb);
dp[i][i+len-1]=min(dp[i][i+len-1],cost+dp[i][j-1]+dp[j][i+len-1]);
}
}
}
return dp[0][n-2];
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[51][51];
class Assemble {
public: int minCost(vector<int> connect) {
int n=connect.size();
FORE(i,0,n+1)FORE(j,0,51)dp[i][j]=1e+9;
FORE(i,0,n+1)dp[i][i]=0;
FORE(len,2,n){
for(int i=0;i+len-1<=n-2;i++){
for(int j=i+1;j<=i+len-1;j++){
int sizea=j-i;
int sizeb=(i+len-1)-j+1;
int cost=(connect[i]+sizea)*connect[j]*(connect[i+len]+sizeb);
dp[i][i+len-1]=min(dp[i][i+len-1],cost+dp[i][j-1]+dp[j][i+len-1]);
}
}
}
return dp[0][n-2];
}
};