問題
様々な商品が存在し、各商品についてexpenseの金額を投資するとptime後にrevenueの収入が得られることがわかっている。
最初にＣ円持っており、これをＤ円にしたいとき、最短でかかる時間を求める。
ただし、そのような場合がないときはー１を返す。
解き方
ｄｐを漸化的に更新していく問題。
ptimeは最大10であり、Dは最大10^5であるため、
dpのサイズを10^6確保して各時間における最大の所持金額を逐次更新していく。
最後に、最初にDを超える時間を返してあげればよい。
コード
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 BusinessPlan {
public:
int howLong(vector<int> expense, vector<int> revenue, vector<int> ptime, int C, int D) {
int n=expense.size();
if(C>=D)return 0;
int dp[100001];
FORE(i,0,100001)dp[i]=1e+9;
dp[C]=0;
FORE(i,C,D)if(dp[i]!=1e+9){
FORE(j,0,n){
if(i>=expense[j]){
int rev=min(i-expense[j]+revenue[j],D);
dp[rev]=min(dp[rev],dp[i]+ptime[j]);
}
}
}
return dp[D]==1e+9 ? -1 : dp[D];
}
};
#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 BusinessPlan {
public:
int howLong(vector<int> expense, vector<int> revenue, vector<int> ptime, int C, int D) {
int n=expense.size();
if(C>=D)return 0;
int dp[100001];
FORE(i,0,100001)dp[i]=1e+9;
dp[C]=0;
FORE(i,C,D)if(dp[i]!=1e+9){
FORE(j,0,n){
if(i>=expense[j]){
int rev=min(i-expense[j]+revenue[j],D);
dp[rev]=min(dp[rev],dp[i]+ptime[j]);
}
}
}
return dp[D]==1e+9 ? -1 : dp[D];
}
};