pku 1276 Cash Machine

桃扇骨 2022-08-13 12:51 25阅读 0赞

\#include <iostream> using namespace std; int num\[11\]; int v\[11\]; int flag\[100001\]; int main() \{ int W, n; while(scanf("%d", &W) != EOF) \{ scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d%d", &num\[i\], &v\[i\]); if(!W || !n) \{ printf("0/n"); continue; \} memset(flag, 0, sizeof(flag)); flag\[0\] = true; int max = 0; for(int i = 1; i <= n; ++i) for(int j = max; j >= 0; --j) if(flag\[j\]) \{ for(int k = 0; k <= num\[i\]; ++k) \{ int temp = j+k\*v\[i\]; if(temp > W) break; if(max < temp) max = temp; if(!flag\[temp\]) flag\[temp\] = true; \} \} printf("%d/n", max); \} return 0; \} //这是dp?叫穷举更合适 //不过我还是要记住这个方法 //below program is TLE /\*\#include <iostream> using namespace std; int num\[11\]; int v\[11\]; int c\[11\]\[100001\]; int main() \{ int W, n; while(scanf("%d", &W) != EOF) \{ scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d%d", &num\[i\], &v\[i\]); if(!W || !n) \{ printf("0/n"); continue; \} memset(c, 0, sizeof(c)); for(int i = 1; i <= n; ++i) \{ for(int j = 1; j <= W; ++j) \{ int max = 0; for(int k = 0; k <= num\[i\]; ++k) if(j-k\*v\[i\] >= 0) \{ if(c\[i-1\]\[j-k\*v\[i\]\]+k\*v\[i\] > max) max = c\[i-1\]\[j-k\*v\[i\]\]+k\*v\[i\]; \} else break; c\[i\]\[j\] = max; \} \} printf("%d/n", c\[n\]\[W\]); \} return 0; \}\*/

发表评论取消回复

表情：

评论列表（有 0 条评论，25人围观）

还没有评论，来说两句吧...

相关阅读

相关 pku 1276 Cash Machine

\include <iostream> using namespace std; int num\[11\]; int v\[11\]; int flag\[100001\];

桃扇骨/ 2022年08月13日 12:51/ 0 赞/ 26 阅读

相关 POJ 1276-Cash Machine（多重部分和-dp）

Cash Machine <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS

拼搏现实的明天。/ 2022年07月12日 03:59/ 0 赞/ 180 阅读

相关 pku 3176

\include<stdio.h> int str\[351\]\[351\]; int main() \{ int n,i,j; // freopen("

小鱼儿/ 2022年06月17日 23:29/ 0 赞/ 152 阅读

相关 POJ 1276

Cash Machine <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS

红太狼/ 2022年06月16日 01:25/ 0 赞/ 96 阅读

相关 NYOJ 1276 机器设备【dfs】

机器设备题目描述 > Alpha 公司设计出一种节能的机器设备。它的内部结构是由 N 个齿轮组成。整个机器设备有 > 一个驱动齿轮，当启动它时，它立即按 10

- 日理万妓/ 2022年05月24日 22:12/ 0 赞/ 28 阅读

相关 hdu 三部曲 Cash Machine

Problem Description A Bank plans to install a machine for cash withdrawal. The machine

冷不防/ 2022年01月05日 15:29/ 0 赞/ 286 阅读

相关 Cash flow

Today,we learn about the cash flow. Cash flow summary: 1.The cash flow identity:(现金恒等式

r囧r小猫/ 2021年12月17日 08:15/ 0 赞/ 362 阅读

相关 HDOJ-三部曲-多重背包-1014-Cash Machine

通过这道题我基本了解了利用二进制对多重背包问题进行优化的思想。 Cash Machine <table> <tbody> <tr> <td><

雨点打透心脏的1/2处/ 2021年12月11日 12:29/ 0 赞/ 233 阅读

相关 bitcoin cash 比特币现金的新地址格式cash addr

Bitcoin Cash，老的比特币格式的地址被称为Legacy（遗产）地址，升级节点至0.16.2后，所有的RPC地址展示都用了CashAddr格式，包括listunspen

柔情只为你懂/ 2021年07月29日 01:54/ 0 赞/ 586 阅读

相关 bitcoin cash的地址格式 cash addr 简介

摘要这篇文章主要阐述用于bitcoin cash的地址格式。它是一种base32编码格式，使用BCH 代码作为校验和，可以直接用于链接或QR码。这种格式重用了Bec

傷城~/ 2021年07月28日 19:17/ 0 赞/ 482 阅读