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; }