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];
		}
};