偷天换日 树形DP+背包
2024-08-29 19:20:58
A. 偷天换日
内存限制：256 MiB 时间限制：1000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
题目描述
神偷对艺术馆内的名画垂涎欲滴准备大捞一把。艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就是分为两个走廊。每个展览厅内都
有若干幅画，每幅画都有一个价值。经过走廊和偷画都是要耗费时间的。警察会在第n秒到达进口，在不被逮捕的情况下你最多能得到的价值
输入格式
第一行一个整数 n
第二行若干组整数，对于每组整数（t,x），t表示进入这个展览厅或经过走廊要耗费t秒的时间，若x>0表示走廊通向的展览厅内有x幅画,接下来x对整数(w,c)表示偷一幅价值为w的画需要c秒的时间。若x=0表示走廊一分为二。
输入是按深度优先给出的。
输出格式
仅一个整数，表示能获得的最大价值。
样例
样例输入
50
5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4
样例输出
1500
数据范围与提示
n≤600；t，c≤5；x≤30
房间和走廊数不超过300个。
注意题目要求你在不被逮捕的情况下得到最多的价值
样例的输入对应于
思路：递归建边，同时进行背包DP+决策
注意，fm数组表达的含义，因为要加上走廊的时间！！
#include<bits/stdc++.h>
#define re register int
#define ll long long
using namespace std;
ll t,n,st,ust;
ll w,c;
ll fm[1100][1100];
void in(int st)
{
ll a,b;
scanf("%lld%lld",&a,&b);
if(b==0)
{
in(st<<1);
in(st<<1|1);
for(re i=n-a*2;i>=0;i--)
{
for(re j=i;j>=0;j--)
{
fm[st][i+a*2]=max(fm[st][i+a*2],fm[st<<1][j]+fm[st<<1|1][i-j]);/*cout<<fm[st<<1][j+2*a]+fm[st<<1|1][i-j]<<endl;*/
}
}
}
else
{
for(re i=1;i<=b;i++)
{
scanf("%lld%lld",&w,&c);
for(re j=n;j>=c+a*2;j--)
fm[st][j]=max(fm[st][j],fm[st][j-c]+w)/*,cout<<fm[st][j]<<endl*/;
}
}
//cout<<"a="<<a<<" b="<<b<<endl;
// return;
}
int main()
{
scanf("%lld",&n);
n--;
in(1);
/*for(int i=1;i<=n;i++)
cout<<fm[1][i]<<endl;*/
printf("%lld",fm[1][n]);
return 0;
}
最新文章
- 到爱尔兰敲代码 / Come, Coding in Ireland
- html初学者了解的笔记02
- msvc2013编译qt5.6源码
- 《介绍一款开源的类Excel电子表格软件》续：七牛云存储实战（C#）
- 改数(洛谷 U5398)
- SD卡驱动分析(一)
- ODBC连接mysql
- grep是模糊匹配
- .NET_Framework_version_history
- 【Android Studio 小技巧】一键查看文件方法结构目录File Structure
- linux命令之vim使用-（转）vim的保存文件和退出命令
- 微软推荐的Get a code signing certificate流程和链接
- boost信号量 boost::interprocess::interprocess_semaphore的用法
- html5 存储篇（一）
- bzoj 1047 : [HAOI2007]理想的正方形 单调队列dp
- vs 文件头自动添加注释
- HTML的基础复习
- IntelliJ IDEA设置统一编码utf-8
- gradle2.0笔记——让项目升级到gradle2.0
- [Swift]LeetCode856. 括号的分数 | Score of Parentheses