bzoj3384[Usaco2004 Nov]Apple Catching 接苹果*&&bzoj1750[Usaco2005 qua]Apple Catching* - Android

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

bzoj3384[Usaco2004 Nov]Apple Catching 接苹果

bzoj1750[Usaco2005 qua]Apple Catching

题意：

两棵树，每分钟会从其中一棵树上掉一个苹果下来，捡苹果的人只愿意W次，问初始在树1处最多能捡多少苹果。分钟数≤1000，W≤30。

题解：

dp。f[i][j][0/1]表示第i分钟移动了j次现在在第2/1棵树下。具体看代码。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 1010
#define INF 0x3fffffff
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
bool a[maxn]; int f[][][],n,w,x,y,ans;
int main(){
n=read(); w=read(); inc(i,,n)a[i]=read()&; x=; y=;
inc(i,,w)f[x][i][]=; inc(i,,w)f[x][i][]=; f[x][][]=-INF;
inc(i,,n+){
if(!a[i-])f[y][][]=f[x][][]+,f[y][][]=f[x][][];
else f[y][][]=f[x][][],f[y][][]=f[x][][]+;
inc(j,,w){
if(!a[i-])f[y][j][]=max(f[x][j-][],f[x][j][]+),
f[y][j][]=max(f[x][j-][]+,f[x][j][]);
else f[y][j][]=max(f[x][j-][]+,f[x][j][]),
f[y][j][]=max(f[x][j-][],f[x][j][]+);
}
swap(x,y);
}
inc(i,,w)ans=max(ans,max(f[x][i][],f[x][i][])); printf("%d",ans); return ;
}

20161017

bzoj3384[Usaco2004 Nov]Apple Catching 接苹果&&bzoj1750[Usaco2005 qua]Apple Catching的更多相关文章

bzoj1750 [Usaco2005 qua]Apple Catching
Description It is a little known fact that cows love apples. Farmer John has two apple trees (which ...
BZOJ 3384&colon; [Usaco2004 Nov]Apple Catching 接苹果( dp )
dp dp( x , k ) = max( dp( x - 1 , k - 1 ) + *** , dp( x - 1 , k ) + *** ) *** = 0 or 1 ,根据情况 (BZOJ 1 ...
3384/1750&colon; [Usaco2004 Nov]Apple Catching 接苹果
3384/1750: [Usaco2004 Nov]Apple Catching 接苹果 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 18 Solv ...
bzoj 3384&colon; [Usaco2004 Nov]Apple Catching 接苹果
双倍经验题... -->1750 dp!! 3384: [Usaco2004 Nov]Apple Catching 接苹果 Time Limit: 1 Sec Memory Limit: 12 ...
苹果将通过新Apple TV打造电视游戏平台欲发力家庭游戏（转）
据<纽约时报>报道,9月10日凌晨1时举行的苹果发布会上将会公布新版Apple TV设备,还会推出TV版App Store.新设备以游戏作为主要卖点,图形性能将大幅提升. 苹果2015年秋 ...
BZOJ 3385&colon; [Usaco2004 Nov]Lake Counting 数池塘
题目 3385: [Usaco2004 Nov]Lake Counting 数池塘 Time Limit: 1 Sec Memory Limit: 128 MB Description 农夫 ...
3386/1752&colon; [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家
3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家 Time Limit: 1 Sec Memory Limit: 128 MBSubmit ...
3385&colon; [Usaco2004 Nov]Lake Counting 数池塘
3385: [Usaco2004 Nov]Lake Counting 数池塘 Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 22 Solved: 21 ...
P3384&colon; [Usaco2004 Nov]Apple Catching 接苹果
一道DP题, f[i,j,k] 表示第 k 时刻由 1 位置变换 j 次到达当前 i 棵树注意也要维护变换 0 次的情况. var i,j,k,t,w,now:longint; tree ...

随机推荐

Apache Commons 工具集使用简介
Apache Commons包含了很多开源的工具,用于解决平时编程经常会遇到的问题,减少重复劳动.我选了一些比较常用的项目做简单介绍.文中用了很多网上现成的东西,我只是做了一个汇总整理. 一.Comm ...
操作系统——IO缓存技术
一.为什么引入缓存技术为了解决cpu速度和外部设备速度不匹配的问题. 降低了io对cpu的中断的次数.每进行一次IO设备的时间都非常长,所以把数据先放入缓冲区,再进行IO操作. 二.缓冲技术的实现 ...
简谈python反射
写出一个简单类:import sysclass webserver(object): def __init__(self,host,post): self.host = host self.post ...
对var的新笔记
今天看阮老师的ES6入门时,看见一个对我来说从没想到过的var赋值变量导致的错误,故记录一下 var tmp = new Date(); function f() { console.log(tmp) ...
golang注意问题
关于slice 我们都知道slice是在通过参数传递的时候传递的是引用 slice的appen操作是有返回值的,并不改变原值例如 b := [],,,} c:=append(b, ) // b 不变 ...
P4313 文理分科
思路遇到这种利益冲突的最终利益最大化问题考虑转化为最小割,使得损失的价值最小相当于文科是S,理科是T,选出最小割就是确定损失代价最小的方案然后就把S向每个点连一条cap=art[i][j]的边 ...
（11）shutil模块（文件处理模块）
shutil模块的格式 shutil.copyfileobj(文件1,文件2) #将文件1的数据覆盖copy给文件2 import shutil f1 = open("1.txt&quo ...
Qt绘图
Qt绘图的设置 QPainter::Antialiasing // 反锯齿 QPainter::TextAntialiasing // 文字反锯齿 QPainter::SmoothPixmapTran ...
成员函数查找[条款24]---《C++必知必会》
调用一个成员函数,涉及三个步骤:第一步,编译器查找函数的名字:第二部,从可用候选者中选择最佳匹配函数:第三步,检查是否具有访问该函数的权限. #include<iostream> usin ...
BZOJ3687 简单题【bitset】
BZOJ3687 简单题 Description 小呆开始研究集合论了,他提出了关于一个数集四个问题: 1．子集的异或和的算术和. 2．子集的异或和的异或和. 3．子集的算术和的算术和. 4．子集的算 ...