POJ 2642 The Brick Stops Here 0-1背包
2024-08-31 19:43:46
poj: http://poj.org/problem?id=2642
大意:
给出n(n<=200)块黄铜合金,还有它们的浓度和价钱。给出若干个个询问使它们在n块中取 M 块 使得这M块合金的浓度在[cMin*M, cMax*M]这个区间内所花费的价格最少。
这里很详细了。。。。http://blog.sina.com.cn/s/blog_9b95c19e010192vl.html
设计状态dp [i][j][v]表示在i个中买不超过价值为v的物品j件。
include<cstdio>
const int INF=999999;
const int MAXN=20000+10;
int w[201],p[201];
int dp[21][MAXN];
int main()
{
int N,M;
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d%d",&w[i],&p[i]); for(int i=0;i<21;i++)
for(int j=0;j<MAXN;j++)
dp[i][j]=INF; int maxnum= N >20? 20: N;
dp[0][0]=0; for(int i=1;i<=N;i++)
{
for(int j=20000;j>=w[i];j--)
for(int k=1;k<=maxnum;k++)
if(dp[k-1][j - w[i] ]!=INF)
dp[k][j] = dp[k][j] < ( dp[k-1][j - w[i] ]+ p[i] )? dp[k][j] : ( dp[k-1][j - w[i] ]+ p[i] );
} int kase;
scanf("%d",&kase); for(int ri=0;ri<kase;ri++)
{
int L,R;
scanf("%d%d%d",&M,&L,&R);
L*=M;
R*=M; int ans=INF;
for(int i=L;i<=R;i++)
if(ans > dp[M][i] )
ans=dp[M][i]; if(ans==INF)
printf("impossible\n");
else
printf("%d\n",ans);
}
}
最新文章
- [翻译]lithium 安装
- mysql 范式和反范式
- WPF系列:无边框窗口
- 尾递归(Tail Recursion)和Continuation
- IOS网络开发(一)
- C# 通用验证类 支持 WPF,MVC,Winform
- onActivityResult调用不到的问题
- PHP创建定义数组
- aop编程 环绕round
- 浅谈PipelineDB系列一: Stream数据是如何写到Continuous View中的
- 超详细 值得收藏 linux CentOS 7 配置Apache服务【转发+新增】
- Vue中的$set的使用
- python3 函数传参练习 全局变量与局部变量 的理解
- 【Linux】常见基础命令之系统操作
- python之路--动态传参,作用域,函数嵌套
- codeforces279B
- Javascript扩展Date的prototype实现时间format函数 2017-06-29T09:10:00.000Z日期转换
- 20181013xlVba计算优秀率及合格率
- Win8交互UX——用于 Windows 的触摸交互
- 电脑CPU开机上电后的第一条指令
热门文章
- 【DRF视图】
- UVALive 6527 Counting ones dfs(水
- 26.多线程join detach
- 1、Task类构造函数
- C#之使用app.config可记录数据,下次打开可读取记录的数据
- 理解宏的使用 extern
- restcontroller和controller区别
- Core Animation 文档翻译—附录A(Layer样貌相关属性动画)
- 1.2 Use Cases中 Website Activity Tracking官网剖析(博主推荐)
- Spring学习总结(7)——applicationContext.xml 配置文详解