SRM 598 DIV1 Easy - BinPacking (○×)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12861&rd=15710複数のアイテムが与えられ、それを瓶に格納したい。
１つの瓶には重さ３００までのアイテムしか入れられない。
各アイテムの重さがわかっているとき、最低でいくつ瓶が必要か求める。
解き方
・問題文だけを考えると、かなりの数の組み合わせがありそう。
・条件をみると、ひとつのアイテムの重さは１００～３００．
・これから、１つの瓶に入るアイテムは１～３つ。
・アイテムの重さが２０１以上であれば１つの瓶には１つしか入らない。
・重さが１００であるアイテムが３つあれば１つの瓶に３つ入れられる。
・残りはソートして、一番大きいアイテムと小さいアイテムの合計が３００以下であれば
一つに入れて、そうでなければ大きいアイテム１つだけ瓶に入れる。
・上記の条件を貪欲法で、と思ったが
１００のアイテムを３つ入れるケースと一番大きいアイテムと
小さいアイテムの２つを入れるケースでは、どちらがよいかは選択できない。
・こういうときはｄｐに切り替える。
→System Passed
コード
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()
int dp[60][60];
vector<int> items;
class BinPacking {
public:
int rec(int l,int r){
if(l>r)return 0;
if(l==r)return 1;
if(dp[l][r]!=-1)return dp[l][r];
int ret=1e+9;
if(l+2<=r && items[l]==100 && items[l+1]==100 &&items[l+2]==100)ret=min(ret,1+rec(l+3,r));
if(items[l]+items[r]<=300)ret=min(ret,1+rec(l+1,r-1));
ret=min(ret,1+rec(l,r-1));
ret=min(ret,1+rec(l+1,r));
return dp[l][r]=ret;
}
int minBins(vector<int> item) {
int n=item.size();
items=item;
sort(all(items));
memset(dp,-1,sizeof(dp));
return rec(0,n-1);
}
};
#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()
int dp[60][60];
vector<int> items;
class BinPacking {
public:
int rec(int l,int r){
if(l>r)return 0;
if(l==r)return 1;
if(dp[l][r]!=-1)return dp[l][r];
int ret=1e+9;
if(l+2<=r && items[l]==100 && items[l+1]==100 &&items[l+2]==100)ret=min(ret,1+rec(l+3,r));
if(items[l]+items[r]<=300)ret=min(ret,1+rec(l+1,r-1));
ret=min(ret,1+rec(l,r-1));
ret=min(ret,1+rec(l+1,r));
return dp[l][r]=ret;
}
int minBins(vector<int> item) {
int n=item.size();
items=item;
sort(all(items));
memset(dp,-1,sizeof(dp));
return rec(0,n-1);
}
};
