SOSUSOSU

假装这是一个正经的页面

[51nod1201整数划分]dp啊啊啊

我实在不知道该怎么起名emmmmm
一开始是这么想的:

dp[i][j] = i的和,最大数不大于j的方案数
dp[i][j] = sum(dp[i – j][k])(0<k<=min(j,i-j))

然后数组开不下,跑也跑不动。。。

于是就这样:

dp[i][j] = i的和, 拆成j个数的方案
dp[i][j] = dp[i – j][j] + dp[i – j][j – 1]

发现并不用开5w*5w,而是5w*sqrt(10w)

然后就没有然后了

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注