Day9 - D - Piggy-Bank POJ - 1384
But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!
Input
Output
Sample Input
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
Sample Output
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible. 思路:完全背包问题,dp[i][j]表示前i种硬币,重量为j时达到的最小值,考虑最直观情况,dp[i][j]=min(dp[i-1][j-k*w]+k*c)(0<=k<=j/w),但此式在计算时有重复,例如在计算dp[i][j-w]时候,计算了dp[i-1][j-w-n*w]+n*c(1<=n<=(j/w)-1),也就是当1<=k时,以此类推,计算dp[i][j]时候就只需要算min(dp[i-1][j],dp[i][j-w])即可,相当于dp[i][j-w]已经把1<=k的答案算出来了,再用滚动数组优化即可
const int INF = 0x3f3f3f3f; int dp[], w[], c[]; int main() {
ios::sync_with_stdio(false), cin.tie();
int T;
cin >> T;
while(T--) {
int E, F, V, N;
cin >> E >> F >> N;
V = F - E;
for(int i = ; i <= V; ++i) dp[i] = INF;
for(int i = ; i <= N; ++i) cin >> c[i] >> w[i];
for(int i = ; i <= N; ++i) {
for(int j = w[i]; j <= V; ++j)
dp[j] = min(dp[j], dp[j-w[i]]+c[i]);
}
if(dp[V] < INF) cout << "The minimum amount of money in the piggy-bank is " << dp[V] << ".\n";
else cout << "This is impossible.\n";
}
return ;
}
最新文章
- JVM内存分配策略
- STM32的DMA
- 优酷、YouTube、Twitter及JustinTV视频网站架构设计笔记
- eclipse中clean操作中如何将validating除去
- hdoj 1231 最大连续子序列
- html5生成柱状图(条形图)
- ARM 开发板嵌入式linux系统与主机PC通过串口传输文件
- jQuery 随滚动条滚动效果 (固定版)
- 遇到Audio/Speech相关问题,如何抓取log
- CentOs Linux 常见命令
- 监控利器 sysdig - 每天5分钟玩转 Docker 容器技术(79)
- 浅谈我的MongoDB学习(一)
- Python 文件的输入与输出
- 04_Weblogic之受管服务器:配置受管服务器,启动受管服务器,解决因为强制关闭Weblogic之后导致启动有问题的问题,配置boot.properties
- PHP安装APC扩展,亲测成功
- c语言程序操作
- Oracle使用学习笔记(二)_Sql语句
- php安装扩展
- p1460 Healthy Holsteins
- IDEA2018.1安装配置文档