SRM 596 DIV2 Middle - ColorfulRoad (○○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12837
複数のタイルからなる１列の道路があり、各タイルは赤、緑、青のいずれかの色が塗られている。
また、最初のタイルは赤色である。
このタイルからスタートし、赤→緑→青→赤・・・の順で右側にあるタイルにジャンプできる。
ただし、ジャンプしたときにその距離の２乗のコストがかかる。
このとき、ゴールまで到達するのに最小のコストを求める。
ゴールまでたどり着けない場合は－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()
class ColorfulRoad {
public: int getMin(string road) {
int n=road.size();
int R[n];
memset(R,0,sizeof(R));
FORE(i,0,n){
if(road[i]=='G')R[i]=1;
else if(road[i]=='B')R[i]=2;
}
int dp[n];
FORE(i,0,n)dp[i]=1e+9;
dp[0]=0;
FORE(i,0,n)FORE(j,i+1,n)if(R[j]==((R[i]+1)%3)){
dp[j]=min(dp[j],dp[i]+(j-i)*(j-i));
}
return dp[n-1]==1e+9 ? -1 : dp[n-1];
}
};
#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()
class ColorfulRoad {
public: int getMin(string road) {
int n=road.size();
int R[n];
memset(R,0,sizeof(R));
FORE(i,0,n){
if(road[i]=='G')R[i]=1;
else if(road[i]=='B')R[i]=2;
}
int dp[n];
FORE(i,0,n)dp[i]=1e+9;
dp[0]=0;
FORE(i,0,n)FORE(j,i+1,n)if(R[j]==((R[i]+1)%3)){
dp[j]=min(dp[j],dp[i]+(j-i)*(j-i));
}
return dp[n-1]==1e+9 ? -1 : dp[n-1];
}
};
