SRM367 div2 hard
メモ化再帰するだけ。
rec(s)でs以降のデータを送るときの最小のパケット数を求める。
実際はオフセットデータも送らないといけなんじゃね。
#include <algorithm> #include <climits> #include <cstdio> #include <cstring> #include <vector> #include <utility> typedef long long LL; using namespace std; class ProgrammingDevice { public: int n; LL maxData; LL cache[50]; vector<pair<int,int> > data; LL rec(int s) { if(s==n) return 0; if(cache[s]!=-1) return cache[s]; cache[s]=LLONG_MAX; for(int e=s;e<n;e++) { LL r=0; LL d=data[e].first+data[e].second-data[s].first; r=d/maxData+(d%maxData==0)?0:1+rec(e+1); cache[s]=min(cache[s],r); } return cache[s]; } int minPackets(vector <int> offset, vector <int> size, int _maxData) { n=offset.size(); maxData=_maxData; for(int i=0;i<n;i++) data.push_back(make_pair(offset[i],size[i])); sort(data.begin(),data.end()); return rec(0); } };