SRM367 div1medium
問題概要
あるデバイスに送らななければならないデータがその始まりのアドレスと大きさの形で渡される。
データはパケットに分けて送らなければならない。
そのパケットはメインデータとオーバーヘッド部分から成る。
このとき送らなければならない最小のバイト数を求めよ。
要はどこからどこまでのデータをまとめて送るかということが大切。
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm367
↑の中にあるサンプルソースコードが非常にわかり易い。
#include <vector> using namespace std; typedef long long LL; class DeviceProgramming { public: LL neededBytes(LL maxPacketSize,LL overhead,LL size) { LL maxInfo=maxPacketSize-overhead; LL packetsNeeded=((size%maxInfo==0)?size/maxInfo:size/maxInfo+1); return size+packetsNeeded*overhead; } LL minBytes(vector <int> offset, vector <int> size, int maxPacketSize, int overhead) { int n=offset.size(); LL DP[60]; vector<int> st,fn; for(int i=0;i<n;i++) { st.push_back(offset[i]); fn.push_back(offset[i]+size[i]-1); } for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(st[i]>st[j]) { swap(st[i],st[j]); swap(fn[i],fn[j]); } for(int i=0;i<n;i++) { DP[i]=neededBytes(maxPacketSize,overhead,fn[i]-st[0]+1); for(int j=0;j<i;j++) DP[i]=min(DP[i],DP[j]+neededBytes(maxPacketSize,overhead,fn[i]-st[j+1]+1)); } return DP[n-1]; } };