SRM 610 DIV1 Middle - AlbertoTheAviator （復習×）
問題
車を運転しており、最初に持っている燃料Fが与えられる。
また、複数の給油ポイントがあり、そこまでにいくのに必要な燃料durationと給油できる燃料refuelが与えられる。
好きな給油ポイントを選んで行ってよいとき、たどりつくことのできる最大の給油ポイントの数を求める。
解き方
給油ポイントの数が５０であるため、Ｏ（５０！）と全探索では解けない。
そのため、順番を考慮しないとｄｐで解くことはできない。
では、どのようにたどる順番があるかを考える。
問題文より、必要な燃料の順では解けないことがわかる。
証明として、refuelの降順にたどることができないかを反例を用いて考える。
仮に、ある給油ポイントがduration[i]、refuel[i]、
それよりもrefuelが少ない給油ポイントduration[j]、refuel[j]を考える。
refuelが少ない給油ポイントから多いポイントに行けて、
多い給油ポイントから少ない給油ポイントに行けないとすると、
F-duration[j]+refuel[j]>=duration[i]
F-duration[i]+refuel[i]<duration[j]
式を変形すると、
F+refuel[j]>=duration[i]+duration[j]
F+refuel[i]<duration[i]+duration[j]
refuel[i]>refuel[j]より上記は成立しないので、
少ない給油ポイントから多い給油ポイントに行けるときは、
必ず多い給油ポイントから少ない給油ポイントに行けることがわかる。
よって、refuelの降順にｄｐを適用していけばよい。
コード
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[51][5001];
class AlbertoTheAviator {
public: int MaximumFlights(int F, vector<int> duration, vector<int> refuel) {
int n=duration.size();
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(refuel[i],duration[i]));
sort(p.rbegin(),p.rend());
memset(dp,-1,sizeof(dp));
dp[0][F]=0;
FORE(i,0,n)FORE(j,0,F+1){
if(dp[i][j]==-1)continue;
FORE(k,i,n){
if(j>=p[k].second){
dp[k+1][j-p[k].second+p[k].first]=max(dp[k+1][j-p[k].second+p[k].first],dp[i][j]+1);
}
}
}
int ret=0;
FORE(i,0,n+1)FORE(j,0,F+1)ret=max(ret,dp[i][j]);
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()
int dp[51][5001];
class AlbertoTheAviator {
public: int MaximumFlights(int F, vector<int> duration, vector<int> refuel) {
int n=duration.size();
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(refuel[i],duration[i]));
sort(p.rbegin(),p.rend());
memset(dp,-1,sizeof(dp));
dp[0][F]=0;
FORE(i,0,n)FORE(j,0,F+1){
if(dp[i][j]==-1)continue;
FORE(k,i,n){
if(j>=p[k].second){
dp[k+1][j-p[k].second+p[k].first]=max(dp[k+1][j-p[k].second+p[k].first],dp[i][j]+1);
}
}
}
int ret=0;
FORE(i,0,n+1)FORE(j,0,F+1)ret=max(ret,dp[i][j]);
return ret;
}
};
