問題
http://topcoder.bgcoder.com/print.php?id=1193
銀行強盗がおり、できるだけ多くのダイヤを持って帰りたい。
各部屋は隣り合った扉があり、最初の部屋のみ入り口の扉がある。
また、部屋番号と宝の価値、宝を盗むのに必要な時間が与えられる。
合わせて、各部屋ごとに滞在できる時間も与えられる。
このとき、できるだけ多くの宝を持って部屋をでることのできたときの最大の宝の価値の和を求める。
解き方
各部屋はつながっており、最後には部屋を出ないといけない。
この条件より、各部屋については前の部屋のうち一番短い滞在時間しか、滞在することはできない。
また問題文より、各部屋には一つの宝ではなく、複数種類の宝が存在しているところに注意。
各時刻においてｄｐで走査し、最後に一番高い価値の値を返す。
ここも最後の時間が一番高い価値ではないことに注意。
コード
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 JimmyLightning {
public:
int robTheBank(vector<int> doors, vector<string> diamonds) {
int n=doors.size();
FORE(i,1,n)doors[i]=min(doors[i],doors[i-1]);
vector<pair<int,pair<int,int> > > p;
FORE(i,0,diamonds.size()){
stringstream out(diamonds[i]);
int t[3];
out>>t[0]>>t[1]>>t[2];
p.push_back(make_pair(t[2]-1,make_pair(t[0],t[1])));
}
int time=doors[0];
int dp[time];
memset(dp,0,sizeof(dp));
FORE(i,0,time){
FORE(j,0,p.size()){
int next=i+p[j].second.second;
if(next<doors[p[j].first]){
dp[next]=max(dp[next],dp[i]+p[j].second.first);
}
}
}
int ret=0;
FORE(i,0,time)ret=max(ret,dp[i]);
return ret;
}
};
#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 JimmyLightning {
public:
int robTheBank(vector<int> doors, vector<string> diamonds) {
int n=doors.size();
FORE(i,1,n)doors[i]=min(doors[i],doors[i-1]);
vector<pair<int,pair<int,int> > > p;
FORE(i,0,diamonds.size()){
stringstream out(diamonds[i]);
int t[3];
out>>t[0]>>t[1]>>t[2];
p.push_back(make_pair(t[2]-1,make_pair(t[0],t[1])));
}
int time=doors[0];
int dp[time];
memset(dp,0,sizeof(dp));
FORE(i,0,time){
FORE(j,0,p.size()){
int next=i+p[j].second.second;
if(next<doors[p[j].first]){
dp[next]=max(dp[next],dp[i]+p[j].second.first);
}
}
}
int ret=0;
FORE(i,0,time)ret=max(ret,dp[i]);
return ret;
}
};