poj 3181 Dollar Dayz(求组成方案的背包+大数)
方案 poj 组成 背包 大数
2023-09-27 14:23:52 时间
可能nyist看见加的背包专题我老去凑热闹,觉得太便宜我了。他们新加的搜索专题居然有密码。
都是兄弟院校嘛!何必那么小气。
回到正题,跟我写的上一篇关于求组成方案的背包思路基本一样,无非就是一个二维费用的背包换成了完全背包。如果说题目有什么亮点的话,那就是大数了。第一遍写的时候瞎了我的狗眼竟然没注意到,我的1A就这么没了。
关于组成方案的叙述,还是看我之前那篇结题报告吧:关于背包组成方案的讨论
#include<stdio.h> #include<string.h> #define N 1005 int dp[N][N]; int flag[N]; int i,j; void Add(int x) { int i; int as=0; flag[j]=flag[j]>flag[x]?flag[j]:flag[x]; for(i=0;i<flag[j];i++) { dp[j][i]=dp[j][i]+dp[x][i]+as; as=0; if(dp[j][i]>=10) { as=1; dp[j][i]%=10; } } if(as) { flag[j]++; dp[j][i]=1; } return ; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { memset(dp,0,sizeof(dp)); memset(flag,0,sizeof(flag)); dp[0][0]=1; flag[0]=1; for(i=1;i<=m;i++) { for(j=i;j<=n;j++) { int x; x=j-i; Add(x); } } for(i=flag[n]-1;i>=0;i--) printf("%d",dp[n][i]); printf("\n"); } return 0; }
相关文章
- Pytest测试框架一键动态切换环境思路及方案
- Terrain方案比较
- 【前端攻略】最全面的水平垂直居中方案与flexbox布局
- 2020年全国大学生智能汽车竞赛山东赛区比赛专家组工作方案
- CSDN线上直播操作测试方案
- 自动化测试技术笔记(三):如何编写技术方案
- Ubuntu 系统的降温方案
- 分布式实时日志:ELK 的部署架构方案
- 413 Request Entity Too Large 问题及方案详细分析
- android新版本适配-android13最全适配方案
- iOS应用架构谈 本地持久化方案及动态部署
- iOS应用架构谈 view层的组织和调用方案
- 微信小程序填坑之路(三):布局适配方案(rpx、px、vw、vh)
- 高通:Wi-Fi联盟新测试方案对LTE-U不公平
- [LeetCode] 879. Profitable Schemes 盈利方案
- 前端依赖管理之模块化方案