UVa-10313 : Pay the Price

問題概要

N<300に対して分割数を求める問題。入力の読み取りが面倒。

acceptされたコード

#include <cstdio>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_N = 300;

vector<int> input;
int64 dp[MAX_N+1][MAX_N+1];

void pre_solve(){
	dp[0][0] = 1;
	for(int i=0; i<=MAX_N; i++){
		for(int j=1; j<=MAX_N; j++){
			dp[i][j] = (i>=j ? dp[i-j][j] : 0) + dp[i][j-1];
		}
	}
}

bool init(){
	string line;
	getline(cin, line);
	stringstream ss(line);
	input.clear();
	int x;
	while(ss >> x){
		input.push_back(x);
	}

	return !input.empty();
}

int64 solve(){
	if((int)input.size() == 1){
		return dp[input[0]][input[0]];
	}
	else if((int)input.size() == 2){
		return dp[input[0]][min(MAX_N, input[1])];
	}
	else if(input[1] == 0){
		return dp[input[0]][min(MAX_N, input[2])];
	}
	else{
		if(input[1] > MAX_N){
			return 0;
		}
		return dp[input[0]][min(MAX_N, input[2])] - dp[input[0]][input[1]-1];
	}
}

int main(){
	pre_solve();
	while(init()){
		printf("%lld\n", solve());
	}

	return 0;
}