|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
//Problem F /* #include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; long long dp[125][125]; void solve(){ memset(dp, 0, sizeof(dp)); for (int i = 1; i <= 120; i++) { dp[i][0] = 1; dp[1][i] = 1; } for (int i = 1; i <= 120; i++) { for (int j = 1; j <= 120; j++) { dp[j][i] = dp[j-1][i]+dp[j][i-j]; } } } int main(){ solve(); int toQuery; while (cin >> toQuery) { cout << dp[toQuery][toQuery] << endl; } return 0; } |
又是一个特定问题了，这个叫拆分数问题（不考虑顺序型）。解法如下（其实是扒来的）：
¤动态规划解题思路：
¤定义状态：dp[x][n]表示只用整数 1~ x 表示出n有多少种方法。
¤状态转移方程：
¤dp[i][n]=dp[i-1][n]+dp[i][n-i]
¤边界条件：
dp[1][k]＝1 (0<=k<=n)
因为对于0~n，只用1去表示的只有一种方法。
其（ren）实（hua）是这样，假如说我们像拆分7，那么我们就是用1～7的数来加合成7了，用1～7表示7可以分开两种看：用1～6表示7，和用1～7表示0，这两种情况，后面那个看起来很sxbk，其实就是7+0啦。然后1～6表示7我们还是不会算，这个又可以分解了，那就是用1～5表示7，和1+6（用1～6表示1），接下来再把1～5表示7拆分为1～4表示7和5+2（用1～5表示2，这会你应该看出来了，5+2中，5不能动只是肯定的，但是2已经不止一种表示方法了），接下来再拆1～4表示7为1～3表示和4+3，然后拆拆拆到1表示7，显然只有一种方法1111111，这样就到达了递推的终点，逐层返回就搞定了。
