TopCoder SRM 367 Div1 Medium DeviceProgramming
問題
メモリに書き込みをしたい。
書き込みたいデータはn個あり、それぞれoffset[i]番地から連続してsize[i]バイトのデータを書き込みたい。
書き込みたい番地以外には、何かを書き込んでも、何も書き込まなくても良い。
一度の書き込みでは、maxPacketSizeバイトのデータをメモリの送信しすることができるが、
そのうちoverheadバイトは無駄になる。
すなわち、一度の書き込みでは最大でmaxPacketSize-overheadバイトのデータを、連続するメモリ領域に書き込むことができる。
全てのデータを書き込むために、最小で何バイトのデータを送信する必要があるか、求めよ。
方針
動的計画法による。
dp[i]を、iバイト目まで書き終えたときの、データ送信量の最小値とする。
DPの更新は、
次の区間をk個カバーしてぴったり終わるか、
k個の区間をカバーしたあと、余りの部分をフルに使って残りの区間の最初に少し書き込むか。
iを全ての整数についてまわすと10^9でTLEなので、
mapを使って、ちょうど端になる部分だけ考えるようにする。
ソースコード
map<int,ll> dp; class DeviceProgramming { public: long long minBytes(vector <int> offset, vector <int> size, int maxPacketSize, int overhead) { int n=offset.size(), sz=maxPacketSize-overhead; vector<pi> d; rep(i,n)d.pb(mp(offset[i],size[i])); sort(all(d)); ll ans=1ll<<60; dp.clear(); dp[0]=0; int j=0; fr(i,dp){ if(i->first>=d[n-1].first+d[n-1].second)ans=min(ans,i->second); while(j<n&&d[j].first+d[j].second<=i->first)j++; for(int k=j;k<n;k++){ ll tmp=i->second, cur=max(i->first,d[j].first); ll w=d[k].first+d[k].second-cur; ll t=(w+sz-1)/sz; tmp+=t*overhead+w; if(!dp.count(d[k].first+d[k].second)|| dp[d[k].first+d[k].second]>tmp)dp[d[k].first+d[k].second]=tmp; tmp=i->second+t*maxPacketSize; if(!dp.count(cur+t*sz)||dp[cur+t*sz]>tmp)dp[cur+t*sz]=tmp; } } return ans; } };