SRM 275 DIV1 Middle -Horoscope

問題

http://topcoder.bgcoder.com/print.php?id=1090

占い師がうらなった、今後数日間の良い日、悪い日のリストがある。
リストは配列で与えられ、良い日は'G'、悪い日は'B'で表わされる。
しかし、その占いは連続でR日間は当たるが、連続でB日間は外れる。

このとき、最も良い日が続く時の、良い日の日数を求める。

解き方

ｄｐで解く問題。
リストは最大で2500、R,Bは最大50であるので、
リストの長さと現在までに続いているRの長さ、Bの長さを状態としてもっておけば計算量O(2500*50*50)として間に合う。

コード

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[2510][2][60];

class Horoscope {

public:

int maxGoodDays(vector<string> predictions, int R, int W) {
string str="";
FORE(i,0,predictions.size())str+=predictions[i];
int n=str.size();

memset(dp,0,sizeof(dp));

FORE(i,0,n)FORE(k,0,59){
if(k<R)dp[i+1][0][k+1]=max(dp[i+1][0][k+1],dp[i][0][k]+(str[i]=='G'));
dp[i+1][1][1]=max(dp[i+1][1][1],dp[i][0][k]+(str[i]=='B'));

if(k<W)dp[i+1][1][k+1]=max(dp[i+1][1][k+1],dp[i][1][k]+(str[i]=='B'));
dp[i+1][0][1]=max(dp[i+1][0][1],dp[i][1][k]+(str[i]=='G'));
}

int ret=0;
FORE(i,0,2)FORE(j,0,60)ret=max(ret,dp[n][i][j]);

return ret;
}

};

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()

string p;
int R,W,dp[2550][55][55],n;

class Horoscope {

public:

int calc(int pos,int rlen,int wlen){
if(pos==n)return 0;
if(dp[pos][rlen][wlen]!=-1)return dp[pos][rlen][wlen];

int ret=0;
if(rlen<R)ret=max(ret,(p[pos]=='G')+calc(pos+1,rlen+1,0));
if(wlen<W)ret=max(ret,(p[pos]=='B')+calc(pos+1,0,wlen+1));

return dp[pos][rlen][wlen]=ret;
}

int maxGoodDays(vector<string> predictions, int R_, int W_) {
R=R_;
W=W_;
memset(dp,-1,sizeof(dp));

p="";
FORE(i,0,predictions.size())p+=predictions[i];
n=p.size();

return calc(0,0,0);
}

};

Share this

Related Posts