01背包显然超时。然后就是一道神dp了。dp[i][j]表示j个数组成i的方案数。O(nsqrt(n))

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
const int nmax=5e4+5;
const int mod=1e9+7;
int dp[nmax][355];
int main(){
int n;scanf("%d",&n);
dp[1][1]=1;
rep(i,2,n) rep(j,1,min(i,350)) dp[i][j]=(dp[i-j][j]+dp[i-j][j-1])%mod;
int ans=0;
rep(i,1,350) ans=(ans+dp[n][i])%mod;
printf("%d\n",ans);
return 0;
}

  

基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题
 收藏
 关注
将N分为若干个不同整数的和,有多少种不同的划分方式,例如:n = 6,{6} {1,5} {2,4} {1,2,3},共4种。由于数据较大,输出Mod 10^9 + 7的结果即可。

 
Input
输入1个数N(1 <= N <= 50000)。
Output
输出划分的数量Mod 10^9 + 7。
Input示例
6
Output示例
4

最新文章

  1. asp.net dataTable转换成Json格式
  2. [sql查询] 重复数据只取一条
  3. Java Native Interface 二 JNI中对Java基本类型和引用类型的处理
  4. 【转】web集群时session同步的3种方法
  5. [docker] 管理docker容器中的数据
  6. Java、JSP获得当前日期的年、月、日
  7. android 下载instagram动态中图片的demo
  8. Static NAT with iptables on Linux
  9. Nginx常用Rewrite伪静态法则
  10. HDOJ 5093 Battle ships 二分图匹配
  11. BestCoder Round #20 部分题解(A,B,C)(hdu5123,5124,5125)
  12. MFC中为菜单或按钮添加快捷键功能
  13. 【社交系统ThinkSNS+研发日记三】基于 Laravel Route 的 ThinkSNS+ Component
  14. JDBCTemplate简化JDBC的操作(一)
  15. vue中实现动态切换不同的值
  16. Centos7上安装java
  17. Spark 官方博文专区(目录)
  18. FCC JS基础算法题(3):Find the Longest Word in a String (找出最长单词)
  19. css3不错的教程
  20. cocos2d-x 开发用到的工具

热门文章

  1. 帝国cms数据还原后提示数据库表不存在怎么解决?
  2. javascript 关于函数的返回值
  3. jquery easyui tab加载内容的几种方法
  4. SQL技术内幕-13 SQL优化方法论之分析实例级别的等待
  5. The first day of HTML
  6. 李洪强iOS开发之OC[011] - 有参方法的声明实现以及调用练习
  7. lintcode :最近公共祖先
  8. mysql新建用户本地无法登录
  9. React-组件嵌套-子组件通过委托向父组件传值
  10. Hibernate笔记——表的的4种继承关系