TopCoder SRM 367 Div1 Medium DeviceProgramming

問題

メモリに書き込みをしたい。
書き込みたいデータはn個あり、それぞれoffset[i]番地から連続してsize[i]バイトのデータを書き込みたい。
書き込みたい番地以外には、何かを書き込んでも、何も書き込まなくても良い。


一度の書き込みでは、maxPacketSizeバイトのデータをメモリの送信しすることができるが、
そのうちoverheadバイトは無駄になる。
すなわち、一度の書き込みでは最大でmaxPacketSize-overheadバイトのデータを、連続するメモリ領域に書き込むことができる。


全てのデータを書き込むために、最小で何バイトのデータを送信する必要があるか、求めよ。

制約条件

n≦50
offset[i]≦10^9
size[i]≦10^9
offsetとsizeによって指定される区間について、どの二つの区間同士にも重なりはない。

方針

動的計画法による。
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;
  }
};