問題
http://community.topcoder.com/stat?c=problem_statement&pm=2921&rd=5851
６面体を左下が重なるように順に大きいものを重ねていく。
そのときの点の数は１、６，１８，２５，４５，６６・・・となる。
また、正の整数Ｎが与えられた時、これを上記の数の組み合わせで表現したい。
どのＮであっても６個以下の組み合わせで表現することができ、
Ｎ＝２６のときが６個の組み合わせの最大数、
Ｎ＝１３０のときが５個の組み合わせの最大数、
Ｎ＝１４６８５８のときが４個の組み合わせの最大数になる。
Ｎが与えられた時、組み合わせる６面体の数の最小の個数を求める。
解き方
Ｎが１３０以下のときはｄｐで全探索を用いる。
それ以上のときは６面体全てのペアの組み合わせの値を求め、さらにその組み合わせでＮを表現することで、４個以下の組み合わせになるので答えが求まる。
コード
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[1000001];
class HexagonalSums {
public:
int minLength(int N) {
vector<int> v;
int prev=1;
for(int x=2;prev<=1000000;x++){
v.push_back(prev);
prev=prev+6*(x-1)-(1+2*(x-2));
}
int len=v.size();
FORE(i,0,N+1)dp[i]=1e+9;
dp[0]=0;
FORE(i,0,len)dp[v[i]]=1;
FORE(i,0,len)FORE(j,0,len)if(v[i]+v[j]<=1000000)dp[v[i]+v[j]]=min(dp[v[i]+v[j]],2);
FORE(i,0,200)for(int j=0;v[j]<=i;j++)dp[i]=min(dp[i],dp[i-v[j]]+1);
if(N<200)return dp[N];
int ret=1e+9;
FORE(i,0,N+1)ret=min(ret,dp[i]+dp[N-i]);
return ret;
}
};
#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[1000001];
class HexagonalSums {
public:
int minLength(int N) {
vector<int> v;
int prev=1;
for(int x=2;prev<=1000000;x++){
v.push_back(prev);
prev=prev+6*(x-1)-(1+2*(x-2));
}
int len=v.size();
FORE(i,0,N+1)dp[i]=1e+9;
dp[0]=0;
FORE(i,0,len)dp[v[i]]=1;
FORE(i,0,len)FORE(j,0,len)if(v[i]+v[j]<=1000000)dp[v[i]+v[j]]=min(dp[v[i]+v[j]],2);
FORE(i,0,200)for(int j=0;v[j]<=i;j++)dp[i]=min(dp[i],dp[i-v[j]]+1);
if(N<200)return dp[N];
int ret=1e+9;
FORE(i,0,N+1)ret=min(ret,dp[i]+dp[N-i]);
return ret;
}
};