我实在不知道该怎么起名emmmmm
一开始是这么想的：
dp[i][j] = i的和，最大数不大于j的方案数
dp[i][j] = sum(dp[i – j][k])(0<k<=min(j,i-j))
dp[i][j] = sum(dp[i – j][k])(0<k<=min(j,i-j))
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <bits/stdc++.h> using namespace std; int n, dp[105][105], ans; int main(){ scanf("%d", &n), dp[1][1] = 1; for(int i = 0; i <= n; i++) dp[0][i] = 1; for(int i = 2; i <= n; i++) for(int j = 1; j <= i; j++) for(int k = 0; k <= min(j - 1, i - j); k++) dp[i][j] += dp[i - j][k]; for(int i = 1; i <= n; i++) ans += dp[n][i]; printf("%d\n", ans); return 0; } |
然后数组开不下，跑也跑不动。。。
于是就这样：
dp[i][j] = i的和， 拆成j个数的方案
dp[i][j] = dp[i – j][j] + dp[i – j][j – 1]
dp[i][j] = dp[i – j][j] + dp[i – j][j – 1]
发现并不用开5w*5w，而是5w*sqrt(10w)
然后就没有然后了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <bits/stdc++.h> #define mo 1000000007 using namespace std; int n, ans, dp[50005][320]; int main(){ scanf("%d", &n), dp[1][1] = 1; for(int i = 2; i <= n; i++) for(int j = 1; j <= sqrt(i * 2); j++) dp[i][j] = (dp[i - j][j] + dp[i - j][j - 1]) % mo; for(int i = 1; i <= sqrt(n << 1); i++) ans = (ans + dp[n][i]) % mo; printf("%d", ans); return 0; } |