First I thought it should be solved using DP, and I gave a standard O(n^2) solution:
#include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; #define REP(i, s, n) for(int i = s; i < n; i ++) typedef long long LL; LL calc(vector<LL> &in) { size_t len = in.size(); LL ret = 0; /* // dp[i][onhand] vector<vector<LL>> dp(len, vector<LL>(len + 1, std::numeric_limits<LL>::min())); dp[0][0] = 0; // no action dp[0][1] = -in[0]; // buy REP(i, 1, len) REP(j, 0, i + 1) { // Choice 1: buy dp[i][j + 1] = std::max(dp[i][j + 1], dp[i - 1][j] - in[i]); // Choice 2: no action dp[i][j] = std::max(dp[i][j], dp[i - 1][j]); // Choice 3: sell all if(j > 0) dp[i][0] = std::max(dp[i][0], in[i] * j + dp[i-1][j]); } ret = *std::max_element(dp[len-1].begin(), dp[len-1].end()); */ vector<LL> pre(len + 1, std::numeric_limits<LL>::min()); pre[0] = 0; pre[1] = -in[0]; vector<LL> now(len + 1, std::numeric_limits<LL>::min()); vector<LL> *ppre = &pre, *pnow = &now; REP(i, 1, len) { REP(j, 0, i + 1) { // Choice 1: buy (*pnow)[j + 1] = std::max((*pnow)[j + 1], (*ppre)[j] - in[i]); // Choice 2: no action (*pnow)[j] = std::max((*pnow)[j], (*ppre)[j]); // Choice 3: sell all if(j > 0) (*pnow)[0] = std::max((*pnow)[0], in[i] * j + (*ppre)[j]); } // swap std::swap(ppre, pnow); (*pnow).assign(len + 1, std::numeric_limits<LL>::min()); } ret = *std::max_element((*ppre).begin(), (*ppre).end()); return ret; } int main() { int t; cin >> t; while(t--) { int n; cin >> n; vector<LL> in(n); REP(i, 0, n) cin >> in[i]; cout << calc(in) << endl; } return 0; }
But all TLE.. so there are must be a O(n) solution, and there is.. what is better than a standard DP in cerntain cases? Greedy.
#include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; #define REP(i, s, n) for(int i = s; i < n; i ++) typedef long long LL; LL calc(vector<LL> &in) { size_t len = in.size(); LL ret = 0; std::reverse(in.begin(), in.end()); LL peak = -1; REP(i, 0, len) { if(in[i] > peak) { peak = in[i]; } else { ret += peak - in[i]; } } return ret; } int main() { int t; cin >> t; while(t--) { int n; cin >> n; vector<LL> in(n); REP(i, 0, n) cin >> in[i]; cout << calc(in) << endl; } return 0; }