SRM 602 DIV1 Easy - TypoCoderDiv1 (復習××)

January 13, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12924&rd=15820

・現在のレートとコンテストごとの点数が与えられる。
・そのコンテストに勝利した場合はその点数が足され、負けた場合は引かれる。ただし０　未満にはならない。
・レートが２２００以上だとbrown、それ未満だとcielの称号になる。
・２つのコンテスト連続でbrownの称号にならないようにする。

このとき、brownとcielの称号が変化する最大の数を求める。

解き方

要素数が５０なので全探索では2^50となり間に合わない。
点数の最大が10^9と全てdpすると間に合わないが、連続してbrownにはならないことを考えると点数が2200までのdp[50][2200]を考えればよい。
または、全状態数は50×2200なのでこちらでdpするとより簡単なコードになる。

コード

map< pair < int, int >, int > p;
vector<int> R;

class TypoCoderDiv1 {

public:

int calc(int pos,int rate){
if(p.count(make_pair(pos,rate)))return p[make_pair(pos,rate)];
if(pos==R.size())return p[make_pair(pos,rate)]=0;

int ret=0;

if(rate>=2200){
int score=rate-min(R[pos],rate);
if(score>=2200)ret=-1000000;
else ret=max(ret,1+calc(pos+1,score));
}else{
int score=rate+R[pos];
if(score>=2200)ret=max(ret,1+calc(pos+1,score));
else ret=max(ret,calc(pos+1,score));

score=rate-min(R[pos],rate);
ret=max(ret,calc(pos+1,score));
}
return p[make_pair(pos,rate)]=ret;
}

int getmax(vector<int> D, int X) {
p.clear();
R=D;
return calc(0,X);
}

};

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 n;
map<pair<int,int>,int> m;
vector<int> R;

class TypoCoderDiv1 {

public:

int rec(int pos,int rate){
if(pos==n)return 0;
if(rate>=2200 && rate-R[pos]>=2200)return -100000;

pair<int,int> cur=make_pair(pos,rate);
if(m.find(cur)!=m.end())return m[cur];

int ret=0;
if(rate<2200)ret=max(ret,rec(pos+1,rate+R[pos])+(rate+R[pos]>=2200));
if(rate-R[pos]<2200)ret=max(ret,rec(pos+1,max(0,rate-R[pos]))+(rate>=2200));

return m[cur]=ret;
}

int getmax(vector<int> D, int X) {
m.clear();
R=D;
n=D.size();
return rec(0,X);
}

};