hdu 1284 钱币兑换问题(动态规划)
2024-08-24 22:44:58
Ac code :
完全背包:
#include<stdio.h>
#include<string.h>
int dp[4][40000];
int main(void)
{
int i,j,n;
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(i=1; i<=3; i++)
{
for(j=0; j<32770; j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-i];
}
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",dp[3][n]);
}
return 0;
}
完全背包-滚动数组法:
#include<stdio.h>
#include<string.h>
int dp[40000];
int main(void)
{
int i,j,n;
memset(dp,0,sizeof(dp));
dp[0]=1;
for(i=1; i<=3; i++)
{
for(j=i; j<32770; j++)
{
dp[j]+=dp[j-i];
}
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",dp[n]);
}
return 0;
}
非背包解法:
#include<stdio.h>
int f(int n)
{
int sum,i,x=n/3;
sum=n/3+1;
for(i=0; i<=x; i++)
{
sum+=((n-i*3)>>1);
}
return sum;
}
int main(void)
{
int n;
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",f(n));
}
return 0;
}
博文中问题分析图来自:
http://blog.csdn.net/u013480600/article/details/40477769
最新文章
- 关于当传过来的值转换成string类型报错的问题
- CSS3--overflow属性
- leetCode191/201/202/136 -Number of 1 Bits/Bitwise AND of Numbers Range/Happy Number/Single Number
- JavaScript 之垃圾回收和内存管理
- java zip文件的解压缩(支持中文文件名)
- 内存修改console
- 利用DIV+CSS制作网页过程中常用的基本概念及标签使
- 动软代码生成与 EntityFramework 实体生成模板
- 也谈SSO,一个简单实用的单点登录Demo
- java web从零单排第二十一期《Hibernate》主键的生成方式,用户增加与显示用户列表
- Android——另外一种增删查改的方式(ContentProvider常用)
- git 基本用法
- anyremote源码分析
- greenplum在执行vacuum和insert产生死锁问题定位及解决方案
- 音频压缩编码 opus 附完整C++代码示例
- 开机出现 grub rescue>; 终端模式修复方法
- 豆瓣API
- java游戏开发杂谈 - 实现游戏主菜单
- 压测过程中出现ops断崖式下跌原因及排解
- 安装grub到U盘分区,实现多系统引导