原题连接: Click https://www.luogu.com.cn/problem/P1025
加强数据: Click https://www.luogu.com.cn/problem/U101024
Solution
参考博客: Click
题目意思非常明确了, 这是一道组合数学的题目. 我就直接讲 dp 解法了.
dp
题意可以转化为将 \(n\) 个苹果放进 \(k\) 个盒子里, 并且不允许空盒.
设 \(f[i][j]\) 代表将 \(i\) 个苹果放入 \(j\) 个盒子中, 那么我们用解决这类问题的常用方法来分析:
我们必须先保证每个盒子非空, 因此在 \(i\) 个苹果中选出 \(j\) 个放入每个盒子.
此时我们剩余 \(i-j\) 个苹果, 我们就是要往已有的一层苹果上加 \(i-j\) 苹果, 求此时的方案数.
现在 \(i-j\) 个苹果可以任意分配了, 也就是分成 \(1\) 份,\(2\) 份,\(3\) 份都是合法的......
得到转移方程:
\[ dp[i][j] = \sum_{k=1}^jdp[i-j][k]\]
枚举 \(i\), 随后枚举 \(j\), 随后枚举 \(k\), 三层循环即可得出答案.
时间复杂度为 \(O(nk^2)\), 预期得分 70 分.
这个或许可以套树状数组优化一下求和......
那么复杂度是 \(O(nk\log k)\), 然而最大的范围 \(nk\) 达到了 \(1.2\) 亿的大小, 再加上个 \(\log\) 铁定超时.
然后你可以发现:
\[dp[i-1][j-1] = \sum_{k=1}^{j-1}dp[i-j][k]\]
为什么会有这样的奇特之处呢? 因为 \(i-j\) 就是 \(i\) 和 \(j\) 的差值, 那么同增同减一个 \(1\),dp 数组的一维下标是不变的, 只是二维的 \(k\) 会少一个 \(dp[i-j][j]\), 那么我们把这个加上就好了.
据此写出转移方程:
\[dp[i][j] = dp[i-1][j-1] + dp[i-j][j]\]
两层循环即可转移, 复杂度就降到 \(O(nk)\) 了, 由于常数小, 可以通过本题.
但交上去......MLE!
空间优化
空间复杂度也是 \(O(nk)\) 的, 但事实上我们只需要用到 \(O(k^2)\) 的内容, 很容易想到滚动数组.
于是写出:
- inline int pos(const int &x)
- {
- return (x % 600) + 1;
- }
- int main()
- {
- scanf("%d%d", &n, &k);
- dp[pos(0)][0] = 1;
- int i, j;
- for (i = 1; i <= n; ++i)
- {
- memset(dp[pos(i)], 0, sizeof(dp[pos(i)]));
- for (j = 1; j <= k && j <= i; ++j)
- dp[pos(i)][j] = (dp[pos(i-j)][j] + dp[pos(i-1)][j - 1]) % 10086;
- }
- printf("%d", dp[pos(n)][k]);
- return 0;
- }
个人预期是能 AC 了, 但实际上...... 第 15 个点冷酷无情地 T 了.
评测机跑得不够快
拯救 TLE
吸了氧还是不能拯救世界之后, 我想起了当年用的一种奇淫技巧......
显然此时 TLE 完全是常数问题, 将内层循环的两个判断改成取 min 逆序后依然无法通过.
常数影响最大的就是 pos 函数了, 于是改成了指针映射, 成功 AC!
指针映射
我们考虑要如何避免 pos 函数的高耗时, 当然想到了预处理. 预处理一遍 pos 数组, 直接访问即可, 这应该也是能卡过的 (没有尝试).
但还有一种更有技巧性, 效率更高的方法: 指针.
开一个 f 数组, 如下:
int *f[maxn];
然后赋值:
f[i] = dp[pos(i)];
那么访问时, 直接:
f[i][j] = ....
为什么会快? 这个很显然了吧...... 事实上, 这种方法比:
dp[pos[i]][j] = ....
要快上不少, 为什么?
因为 \(f[i]\) 存的索引直接加上 \(j\) 就能得到地址, 我们实际上避免了两个大数的乘法, 而使其变成了加法.
举例:
原先访问方式:
dp[x?(m+2)+y]
进行了一次乘法一次加法
解析一下就是:
return dp + (x * (m+2) + y);
而现在的访问方式:
(f[x]+y)
解析一下就是:
return (f + x) + y;
效率提升相当显著.
以上这段是直接 copy 原来那篇树上背包的优化中的内容......
同时注意我们的预处理方式:
- int pointer = 0;
- ++pointer;
- if(pointer>= 600)
- pointer -= 600;
可以避免反复求余的预处理效率损失.
最后第 15 个点跑了 500ms 左右......
- Code
- #include <cstdio>
- #include <cstring>
- using namespace std;
- int n, k;
- int dp[610][610];
- int *f[200100];
- inline int min(const int &a,const int &b){return a<b?a:b;}
- int main()
- {
- scanf("%d%d", &n, &k);
- int p = 0;
- for (int i = 0; i <= n; ++i)
- {
- if (p>= 600)
- p -= 600;
- f[i] = dp[p + 1];
- ++p;
- }
- f[0][0] = 1;
- int i, j;
- for (i = 1; i <= n; ++i)
- {
- memset(f[i], 0, sizeof(f[i]));
- for (j = min(k,i); j; --j)
- f[i][j] = (f[i - j][j] + f[i - 1][j - 1]) % 10086;
- }
- printf("%d", f[n][k]);
- return 0;
- }
[LuoguP1025][数据加强] 数的划分
来源: http://www.bubuko.com/infodetail-3383952.html