B. 整数划分

单点时限: 2.0 sec

内存限制: 512 MB

对于一个给定的正整数 n ，希望你能将它分成仅由数字 1 或 2 或 3 组成的和的形式，问有多少种划分方法。

举个例子： 4 可以被划分成 1+1+1+1 或 2+2 或 3+1 或 2+1+1 这 4 种形式，注意 1+3 和 3+1 视为同一种划分方法。

输入格式

有多组输入，每组输入由一行一个正整数 n 组成，题目保证 1≤n≤32767 ，保证数据组数不超过 200 组。

输出格式

对于每一个 n ，输出题目种所求的划分方法数，一行一个结果。

样例

input

4 5

output

4 5

input

2934 12553

output

718831 13137761

---

AC代码: 

// 本质考察完全背包模型 #include <iostream> using namespace std; const int N = 10010; int f[N]; int main() {     int m;     cin >> m;          int v[] = {0, 1, 2, 3};     f[0] = 1;  // 初始化空集为一种方案     for (int i = 1; i <= 3; i ++ ) {         for (int j = v[i]; j <= m; j ++) {             f[j] = f[j] + f[j - v[i]]; // 朴素做法：f[i][j] = f[i - 1][j] + f[i][j - v[i]]         }     }          cout << f[m] << endl;          return 0; }