問題
複数のデータをメモリに格納したい。
格納したいデータごとに、置きたいメモリ番地とデータサイズが与えられる。
このデータをパケットで伝送して届ける。
パケットについては、パケットの最大サイズとヘッダのサイズが与えられ、この差が１つのパケットごとに実際に送ることのできるデータサイズとなる。
送られたパケットは任意の番地からサイズ分メモリに書きこまれる。
メモリ番地については、データに関係ない部分は空白にしても他のデータを埋めてもよい。
このとき、すべてのデータを格納するために送らなければいけない合計パケットサイズを求める。
解き方
dpで解けそうな問題。
最初は直前のデータのみを考え、ぴったりのサイズ分送るか、送ることのできる最大分のパケットを送るかの２通りで考えたが、ベストな送り方は貪欲ではなく、どのデータからスタートするかに依存する。
そのため、あるデータからあるデータまでのパケットを送るときの最小のパケットサイズを最初に求めてあげ、最後にｄｐで最小値を更新すればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class DeviceProgramming {
public: long long minBytes(vector<int> offset, vector<int> size, int maxPacketSize, int overhead) {
int n=offset.size();
long long payload=maxPacketSize-overhead;
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(offset[i],offset[i]+size[i]));
sort(all(p));
long long a[60][60];
FORE(i,0,60)FORE(j,0,60)a[i][j]=1e+18;
FORE(i,0,n+1)FORE(j,0,n+1)if(i<j){
long long cost=p[j-1].second-p[i].first;
long long cnt=(cost+payload-1)/payload;
a[i][j]=min(a[i][j],cost+cnt*overhead);
}
long long dp[n+1];
FORE(i,0,n+1)dp[i]=1e+18;
dp[0]=0;
FORE(i,0,n+1)FORE(j,0,i){
dp[i]=min(dp[i],dp[j]+a[j][i]);
}
return dp[n];
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class DeviceProgramming {
public: long long minBytes(vector<int> offset, vector<int> size, int maxPacketSize, int overhead) {
int n=offset.size();
long long payload=maxPacketSize-overhead;
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(offset[i],offset[i]+size[i]));
sort(all(p));
long long a[60][60];
FORE(i,0,60)FORE(j,0,60)a[i][j]=1e+18;
FORE(i,0,n+1)FORE(j,0,n+1)if(i<j){
long long cost=p[j-1].second-p[i].first;
long long cnt=(cost+payload-1)/payload;
a[i][j]=min(a[i][j],cost+cnt*overhead);
}
long long dp[n+1];
FORE(i,0,n+1)dp[i]=1e+18;
dp[0]=0;
FORE(i,0,n+1)FORE(j,0,i){
dp[i]=min(dp[i],dp[j]+a[j][i]);
}
return dp[n];
}
};