uva11137递推和DP其实有些类似
发布日期:2021-10-08 15:48:51
浏览次数:12
分类:技术文章
本文共 1284 字,大约阅读时间需要 4 分钟。
这道题大白书上是按递推讲的:
分析:建立多段图。节点(i,j)表示“使用不超过i的整数的立方,累加和为j”这个状态,设d(i,j)为从(0,0)
到(i,j)的路径条数,则最终答案为d(21,n)(因为对于题目范围,22*22*22>n)。
这个多段图的特点是每个结点一步只能走到下一个阶段的结点,因此我们可以一个阶段一个阶段的计算,
代码如下。
#include但其实这题可以当做DP来做,其实就是一个变种的完全背包:#include #include #include #include #include #include #include #include
思路:
dp[i, j]表示前i种货币表示j钱有多少种表示方法。
1. dp[i-1, j] 用前i-1种货币表示j
2. dp[i, j-v] 前i种货币表示j-v,再加上v便是必须有第i种货币来表示j
仔细发现可以压缩成一维数组 dp[i] = dp[i] + dp[i-v]。
代码:
#include#include #include const int MAXN = 10010;long long int dp[MAXN];int a[30];int main(){ int n; for (int i = 1; i <= 21; ++i) a[i] = i * i * i; while (scanf("%d", &n) != EOF) { for (int i = 0; i <= n; ++i) dp[i] = 1; for (int j = 2; j <= 21; ++j) for (int i = a[j]; i <= n; ++i) dp[i] += dp[i-a[j]]; printf("%lld\n", dp[n]); } return 0;}
转载地址:https://blog.csdn.net/ONE_PIECE_HMH/article/details/45540837 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月05日 03时00分03秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
二进制、十进制、十六进制换算
2019-04-28
有符号和无符号数分析
2019-04-28
ASCII码
2019-04-28
linux系统操作常用基础命令
2019-04-28
计算CP、CR、CF1、OP、OR、OF1和mAP的top-3评价指标
2019-04-28
python将嵌套数组转为单层数组
2019-04-28
pytorch打印自定义网络的每层的名称
2019-04-28
解决ubantu只能读取U盘文件,不能将文件复制到U盘里面
2019-04-28
MS-COCO2014数据集标签互译
2019-04-28
MacBook Pro快捷键总结
2019-04-28
解决mac里面打开控制台提示 您需要安装JDK才能使用"java"命令行工具
2019-04-28
reactos操作系统实现(92)
2019-04-28
reactos操作系统实现(93)
2019-04-28
使用Python快速实现显示器关闭和锁住桌面
2019-04-28
reactos操作系统实现(94)
2019-04-28