SRM410: ContiguousCache
(問題概要)
nバイトのメモリ、kバイトのキャッシュを持ったマシンを考える。
キャッシュにはメモリ上の連続したkバイトを載せることが出来る。
キャッシュを更新するには、更新前に載っていなかったバイト数だけコストがかかる。
アクセスするアドレス(a[0], a[1], ...)が前もってわかっていている場合に、最適にキャッシュにデータを乗せるとどれだけコストがかかるか。
(解法)
少し考察するとキャッシュに載せるメモリの先頭アドレスは下記のみを考えればよいような気がする。
(証明はしてないけど、任意の他のアドレスに載せた場合は以下に載せた場合のコスト以上になる)
0, n - k, a[0], a[1], ..., a[0] - k + 1, a[1] - k + 1, ...
ここまでわかれば、あとはよくあるDPなりメモ化再帰で終了。
なんか直感的にはグリーディー的にやればもうひとつオーダー下がる気がするけど、問題のサイズから不要。
typedef long long ll; #include <map> #include <algorithm> #define REP(i,n) for(int i=0; i<(int)(n); i++) #include <queue> #include <set> #include <iostream> #include <sstream> using namespace std; class ContiguousCache { public: long long minimumReads(int n, int k, vector <int> addresses); }; long long ContiguousCache::minimumReads(int n, int k, vector <int> addresses){ vector<int> a; REP(i,addresses.size()){ if(addresses[i] + k <= n) a.push_back(addresses[i]); if(addresses[i] - k >= 0) a.push_back(addresses[i] - k + 1); } a.push_back(0); a.push_back(n - k); sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); map<int, int> memo; REP(i,a.size()) memo[a[i]] = i; const ll inf = 1ll << 60; vector<ll> dp(a.size(), k); REP(i,addresses.size()){ const int address = addresses[i]; vector<ll> next(a.size(), inf); REP(j,a.size()) if(dp[j] != inf){ REP(p,a.size()){ if(a[p] <= address && address < a[p] + k){ const ll cost = min(k, std::abs(a[j] - a[p])); next[p] = min(next[p], dp[j] + cost); } } } dp.swap(next); } return *min_element(dp.begin(), dp.end()); }