半数单集问题

半数单集问题 NOJ1211

#include <iostream>
using namespace std;
typedef long long ll;
int n;
ll dp[1005];
ll rep[1005];
int main(){
    dp[0] = 0;
    for (int i=1;i<=1000;i++){
        dp[i] = 1;
        for (int j=1;j<=i/2;j++){
            dp[i] += dp[j];
            if( ( j>10) && (2*(j/10) <= j%10) )
                dp[i] -= dp[j/10];
        }
    }
    while (cin >> n){
        if (n==0)   break;
        cout << dp[n] << endl;
    }
    return 0;
}

//1981471878
//1935307970