ICPC 国内予選2010C ポロック予想 AOJ1167

かなり初歩的なDPやるだけ。

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int dp[1000005][2];

int main(){
    for(int i = 1;i <= 1000000;i++){
        dp[i][0] = 10000000;
        dp[i][1] = 10000000;
    }

    for(int i = 1; i*(i+1)*(i+2)/6 < 1000000;i++){
        int simen = i*(i+1)*(i+2)/6;
        for(int j = 0; j + simen < 1000000;j++){
            for(int k = 0;k < 2;k++){
                if(k == 1 && simen % 2 == 0) continue;
                dp[j+simen][k] = min(dp[j+simen][k],dp[j][k]+1);
            }
        }
    }
    int n;
    while(true){
        cin >> n;
        if(n == 0) break;
        cout << dp[n][0] << " " << dp[n][1] << endl;
    }
}