点击打开链接poj 3628
思路: 0/1背包
分析:
1 题目抽象出来的话就是0/1背包
2 我们用dp[i][j]表示前i头牛放在高度为j的最小高度,那么我们只要求出
dp[n][B~s]中的最小值,然后减去B即可
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 20;
int n , B , s;
int v[N] , dp[N*1000001];
int solve(){
for(int i = 0 ; i <= s ; i++)
dp[i] = INF;
dp[0] = 0;
for(int i = 1 ; i <= n ; i++)
for(int j = s ; j >= v[i] ; j--)
dp[j] = min(dp[j] , dp[j-v[i]]+v[i]);
int ans = INF;
for(int i = B ; i <= s ; i++)
if(dp[i] >= B)
ans = min(ans , dp[i]);
return ans-B;
}
int main(){
while(scanf("%d%d" , &n , &B) != EOF){
s = 0;
for(int i = 1 ; i <= n ; i++){
scanf("%d" , &v[i]);
s += v[i];
}
printf("%d\n" , solve());
}
return 0;
}
分享到:
相关推荐
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
网上整理的一些poj刷题指南。 poj地址:http://poj.org
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
ACM/icpc的练习题目分类,非常全面的关于poj题目的分类
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
<1> 0-1背包,经典问题 <2>无限背包,经典问题 判定性背包问题 带附属关系的背包问题 <5> + -1背包问题 双背包求最优值 构造三角形问题 带上下界限制的背包问题(012背包) 3.线性的动态规划问题 <1>积木游戏...
北大POJ2676-Sudoku 解题报告+AC代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2586-Y2K Accounting Bug 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
poj2009离线题库 poj2009离线题库
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
晒代码之二——多重背包(POJ1276)
POJ3308-Paratroopers 【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 ...
这是西北工业大学的POJ试题的答案,欢迎下载!