問題
http://topcoder.bgcoder.com/print.php?id=1154
１個、２個、３個・・・とボールを三角形上に積み重ねていく。
このときに内部に存在する三角形は１，４、１０個・・・になる。
Ｎ個を内部に存在する三角形の数の和で現したいとき、
最低何個の三角形が必要になるか求める。
解き方
まず、内部に存在する三角形の個数をＮまで全て調べる。
その後ｄｐを利用する。
今回Ｎは最大３＊１０＾５なので、ｄｐの全探索で間に合う。
コード
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 CannonBalls {
public: int fewestPiles(int n) {
vector<int> p;
for(int x=0,cur=0,add=0;cur<=n;x++){
add+=x;
cur+=add;
p.push_back(cur);
}
int dp[n+1];
FORE(i,0,n+1)dp[i]=1e+9;
dp[0]=0;
FORE(i,0,p.size())if(p[i]<=n)dp[p[i]]=1;
FORE(i,0,n+1)for(int j=0;p[j]<=i;j++)dp[i]=min(dp[i],dp[i-p[j]]+1);
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 CannonBalls {
public: int fewestPiles(int n) {
vector<int> p;
for(int x=0,cur=0,add=0;cur<=n;x++){
add+=x;
cur+=add;
p.push_back(cur);
}
int dp[n+1];
FORE(i,0,n+1)dp[i]=1e+9;
dp[0]=0;
FORE(i,0,p.size())if(p[i]<=n)dp[p[i]]=1;
FORE(i,0,n+1)for(int j=0;p[j]<=i;j++)dp[i]=min(dp[i],dp[i-p[j]]+1);
return dp[n];
}
};