Vijos:P1117数的划分
2024-10-02 04:29:10
描述
将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。
例如:n=7,k=3,下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。
格式
输入格式
输入n,k (6<n<=200,2<=k<=6)
输出格式
一个整数,即不同的分法。
输入:
7 3
输出:
4
记忆化搜索:将n划分为非减的k份防重复
#include<cstdio>
#include<cstring>
using namespace std;
int n,k;
int res;
int dp[][][];
int dfs(int i,int mx,int sum)
{
if(dp[i][mx][sum]!=-)
return dp[i][mx][sum];
if(i==k)
{
if(sum==n)
return dp[i][mx][sum]=;
return dp[i][mx][sum]=;
}
if(sum>=n) return ;
int t=;
for(int j=mx;j<=n;j++)
{
t+=dfs(i+,j,sum+j);
}
return dp[i][mx][sum]=t;
}
int main()
{
memset(dp,-,sizeof(dp));
scanf("%d%d",&n,&k);
res=dfs(,,);
printf("%d\n",res);
return ;
}
最新文章
- asp.netajax开发应用心得-accordation控件的事件处理
- 关于git 操作
- maven - 安装与配置
- perl中常见的语法规则和函数
- 网页缩放对 FLASH的影响
- iOS常用---NSString,NSMutabuleString
- Response.BinaryWrite()方法输出二进制图像
- 数据可视化(4)--jqplot
- HDU 1007 Quoit Design(二分+浮点数精度控制)
- R语言保存文件 Error in save error writing to connection
- 使用WITH AS提高性能简化嵌套SQL(转载)
- 使用jquery trigger 触发a标签的click事件取代window.open方法
- 在ashx和静态文件中使用Session
- 用python的TK模块实现猜成语游戏(附源码)
- 原生js贪吃蛇
- 51Nod1222 最小公倍数计数 数论 Min_25 筛
- Java的程序执行过程与编译原理
- 各个JAVA场景下的内存图
- spring filter 配置
- SQL学习之SQL注入学习总结
热门文章
- OpenCV 入门示例之五:一个复杂点的变换
- CGI的基本原理
- c# 备份数据
- 【BZOJ4520】[Cqoi2016]K远点对 kd-tree+堆
- EasyPlayerPro(Windows)流媒体播放器开发之ffmpeg log输出报错
- git config --system --unset credential.helper 重新输入账号密码
- await 暂停 等待 暂停的是什么
- Jeff Dean 排序时间计算
- 2-phase-commit 3-phase-commit
- thinkphp5 (最棒的php开源框架)