SRM 533 DIV1 Easy - CasketOfStar (復習×)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11781&rd=14726
数字の文字列が与えられる。
ひとつずつ文字を選び、その両端の値をかけたものがスコアになる。
選んだあとはその文字は消滅する。
最初と最後の値になるまでこの処理を繰り返した時、最大となるスコアを求める。
解き方
単純に深さ優先探索を行おうとすると、最大でＯ（４８！）のため
解くことができない。
そこで、処理を逆にできないか考えてみる。
ここで、ある数字を選んで挿入することを考えると
そのときのスコアは一意に定まる。
また、そこから挿入するときの最大のスコアは最初～挿入した場所＋挿入した場所～最後
のスコアになる。
この場合は区間ごとの最大値の判定となり葉の判定が増えるのでｄｐが活用でき、
さらに判定回数も減るのでＯ（５０×５０）ほどになる。
コード
int dp[60][60];
vector<int> w;
class CasketOfStar {
public:
int solve(int l,int r){
if(dp[l][r]!=-1)return dp[l][r];
if(l+1==r)return 0;
FORE(i,l+1,r)dp[l][r]=max(dp[l][r],solve(l,i)+solve(i,r)+w[l]*w[r]);
return dp[l][r];
}
int maxEnergy(vector<int> weight) {
w=weight;
FORE(i,0,60)FORE(j,0,60)dp[i][j]=-1;
return solve(0,weight.size()-1);
}
};
vector<int> w;
class CasketOfStar {
public:
int solve(int l,int r){
if(dp[l][r]!=-1)return dp[l][r];
if(l+1==r)return 0;
FORE(i,l+1,r)dp[l][r]=max(dp[l][r],solve(l,i)+solve(i,r)+w[l]*w[r]);
return dp[l][r];
}
int maxEnergy(vector<int> weight) {
w=weight;
FORE(i,0,60)FORE(j,0,60)dp[i][j]=-1;
return solve(0,weight.size()-1);
}
};
using namespace std;
#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()
class CasketOfStar {
public:
int maxEnergy(vector<int> weight) {
int n=weight.size();
int dp[n][n];
memset(dp,0,sizeof(dp));
FORE(len,3,n+1)FORE(s,0,n-len+1){
int e=s+len-1;
FORE(i,s+1,e)dp[s][e]=max(dp[s][e],dp[s][i]+dp[i][e]+weight[s]*weight[e]);
}
return dp[0][n-1];
}
};
#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()
class CasketOfStar {
public:
int maxEnergy(vector<int> weight) {
int n=weight.size();
int dp[n][n];
memset(dp,0,sizeof(dp));
FORE(len,3,n+1)FORE(s,0,n-len+1){
int e=s+len-1;
FORE(i,s+1,e)dp[s][e]=max(dp[s][e],dp[s][i]+dp[i][e]+weight[s]*weight[e]);
}
return dp[0][n-1];
}
};
