题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5543
题目大意:有n个金条,每个金条有长度和价值,给一个长度为L的容器,当金条在容器两端的时候,只要重心在容器内也可以放下,问最多能获得的价值。
思路:01背包,但是重心怎么处理,最好的肯定是边界情况也就是刚好金条刚好能伸出一半,或者直接只取一根金条然后放在容器里面。
多开一位 dp[i][j][k]代表当前选第i个背包容量为j有k个超出边缘的金条时所能获得的最大价值
状态转移方程 dp[i][j][2]=max(dp[i-1][j-w[i]][2]+v[i],dp[i-1][j-w[i]/2][1]+v[i],dp[i][j][2])
dp[i][j][1]=max(dp[i-1][j-w[i]][1]+v[i],dp[i-1][j-w[i]/2][0]+v[i],dp[i][j][1])
dp[i][j][0]=max(dp[i-1][j-w[i]][0]+v[i],dp[i][j][0])
如果没有第一维i的话,那么j和k都要从大到小搞,很明显dp[j][1]是会影响到dp[j][2]的
处理整除的情况很简单,容器和金条长度都*2就好了,这样就能保证一定整除
最后不要忘了放一个的情况要特判一下
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn=;
long long dp[maxn][];
long long v[maxn],w[maxn];
void init(){
memset(dp,,sizeof(dp));
}
void beibao(int pos,int V) {
for(int i=V;i>=w[pos]/;i--) {
dp[i][]=max(dp[i-w[pos]/][]+v[pos],dp[i][]);
if(i>=w[pos])
dp[i][]=max(dp[i-w[pos]][]+v[pos],dp[i][]);
} for(int i=V;i>=w[pos]/;i--){
dp[i][]=max(dp[i-w[pos]/][]+v[pos],dp[i][]);
if(i>=w[pos])
dp[i][]=max(dp[i-w[pos]][]+v[pos],dp[i][]);
}
for(int i=V;i>=w[pos];i--)
dp[i][]=max(dp[i-w[pos]][]+v[pos],dp[i][]);
}
void solve(int T) {
init(); int n,l;
scanf("%d %d",&n,&l);
l<<=;
long long ans=;
for(int i=;i<=n;i++) {
scanf("%lld %lld",&w[i],&v[i]);
w[i]<<=;
ans=max(ans,v[i]);
}
for(int i=;i<=n;i++) {
beibao(i,l);
}
ans=max(ans,max(dp[l][],max(dp[l][],dp[l][])));
printf("Case #%d: %lld\n",T,ans);
}
int main() {
int T;
scanf("%d",&T);
for(int i=;i<=T;i++) solve(i);
}
HDOJ5543 Pick The Sticks的更多相关文章
-
[HDOJ5543]Pick The Sticks(DP,01背包)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5543 题意:往长为L的线段上覆盖线段,要求:要么这些线段都在L的线段上,要么有不超过自身长度一半的部分 ...
-
The 2015 China Collegiate Programming Contest D.Pick The Sticks hdu 5543
Pick The Sticks Time Limit: 15000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others ...
-
2015南阳CCPC D - Pick The Sticks dp
D - Pick The Sticks Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 无 Description The story happened lon ...
-
CDOJ 1218 Pick The Sticks
Pick The Sticks Time Limit: 15000/10000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others ...
-
2015南阳CCPC D - Pick The Sticks 背包DP.
D - Pick The Sticks Description The story happened long long ago. One day, Cao Cao made a special or ...
-
UESTC 1218 Pick The Sticks
Time Limit: 15000/10000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submit Status ...
-
hdu 5543 Pick The Sticks(动态规划)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5543 题意:给你一根长为m的长木板和一些小木棒,每一根小木棒有它的长度和价值,这些小木棒要放在长木板上 ...
-
DP(01背包) UESTC 1218 Pick The Sticks (15CCPC C)
题目传送门 题意:长度为L的金条,将n根金棍尽可能放上去,要求重心在L上,使得价值最大,最多有两条可以长度折半的放上去. 分析:首先长度可能为奇数,先*2.然后除了两条特殊的金棍就是01背包,所以dp ...
-
uestc oj 1218 Pick The Sticks (01背包变形)
题目链接:http://acm.uestc.edu.cn/#/problem/show/1218 给出n根木棒的长度和价值,最多可以装在一个长 l 的容器中,相邻木棒之间不允许重叠,且两边上的木棒,可 ...
随机推荐
-
visual studio插件开发dll类库免加全局缓存处理办法
1.卸载VSIXProject 2.然后编辑*.csproj 修改如下: 3.重新加载项目 编辑source.extension.vsixmanifest 添加资产: 完事后,直接安装VISX就可以了
-
Android音频系统之AudioFlinger(四)
http://blog.csdn.net/xuesen_lin/article/details/8805096 1.1.1 AudioMixer 每一个MixerThread都有一个唯一对应的Audi ...
-
Mac 系统下将普通文件变为可执行文件
在使用Cocospods时,老是提示我pod文件里面有文稿的东西.后来想到前同事将他变为可执行文件了.所以百度了一下,方法如下: chmod +x (此处是文件的地址) 就可以了
-
网易新闻页面信息抓取 -- htmlagilitypack搭配scrapysharp
最近在弄网页爬虫这方面的,上网看到关于htmlagilitypack搭配scrapysharp的文章,于是决定试一试~ 于是到https://www.nuget.org/packages/Scrapy ...
-
Customer reviews on Lexia3 V48 diagnostic tool in EOBD2.FR
Robert said: Ok, so I bought a Lexia3 interface from EOBD2.FR in 2010. I have had no issues over the ...
-
hdoj 2031 进制转换
进制转换 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submis ...
-
Gengxin讲STL系列目录
引言:有人催我写关于STL的博客#(滑稽) STL嘛,昨晚有人一直逼问我STL名字的由来——STL = Standard Template Library,标准模板库,惠普实验室开发的一 ...
-
ReactJs 的各个版本生命周期、API变化 汇总(一、V16.0.0)
目录 一.React 各个版本之间的纵向对比 二.React 的基础 1.Components and Props 三.React V 16.0.0 1. The Component Lifecycl ...
-
Dapper-小型ORM之王(C#.NET)
ORM:对象关系映射器,它直接将数据库映射到C#对象. 有很多ORM框架可用,Dapper是其中之一,被称为ORM之王. 下面是Dapper主要的一些功能: 速度快,性能好; 更少的代码行 对象映射 ...
-
08:Vigen&#232;re密码
08:Vigenère密码 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB 描述 16世纪法国外交家Blaise de Vigenère设计了一种多表密码加密算法— ...