poj 2385【动态规划】
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 14007 | Accepted: 6838 |
Description
Each minute, one of the two apple trees drops an apple. Bessie, having much practice, can catch an apple if she is standing under a tree from which one falls. While Bessie can walk between the two trees quickly (in much less than a minute), she can stand under only one tree at any time. Moreover, cows do not get a lot of exercise, so she is not willing to walk back and forth between the trees endlessly (and thus misses some apples).
Apples fall (one each minute) for T (1 <= T <= 1,000) minutes. Bessie is willing to walk back and forth at most W (1 <= W <= 30) times. Given which tree will drop an apple each minute, determine the maximum number of apples which Bessie can catch. Bessie starts at tree 1.
Input
* Lines 2..T+1: 1 or 2: the tree that will drop an apple each minute.
Output
Sample Input
7 2
2
1
1
2
2
1
1
Sample Output
6
Hint
Seven apples fall - one from tree 2, then two in a row from tree 1, then two in a row from tree 2, then two in a row from tree 1. Bessie is willing to walk from one tree to the other twice.
OUTPUT DETAILS:
Bessie can catch six apples by staying under tree 1 until the first two have dropped, then moving to tree 2 for the next two, then returning back to tree 1 for the final two.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int dp[][];
int app[]; int main()
{
int T,W;
scanf("%d%d",&T,&W);
memset(dp,,sizeof(dp));
for(int i=;i<=T;i++){
scanf("%d",&app[i]);
}
if(app[]==) dp[][]=;
else dp[][]=;
for(int i=;i<=T;i++){
dp[i][]=dp[i-][]+app[i]%;
for(int j=;j<=W;j++){
dp[i][j]=max(dp[i-][j],dp[i-][j-]);
if(j%+==app[i]) dp[i][j]++;
}
}
int ans=;
for(int i=;i<=W;i++)
ans=max(ans,dp[T][i]);
printf("%d\n",ans);
return ;
}
最新文章
- SQL Server 变更数据捕获(CDC)
- 推荐一个实用的css工具
- ZOJ 1442 Dinner Is Ready 容斥原理 + java大数
- IOS UIWebView引用外部CSS样式(转载)
- hdu acmsteps 2.1.3 Cake
- miniUI子窗口调父窗口方法
- SSIS 控制流和数据流(转)
- C++库研究笔记——操作符重载实现类型转换&这样做的意义
- Android iOS Dribbble风格边栏菜单实现
- ASP.NET 开发者 开始学习ASP.NET Core 2吧
- Muduo阅读笔记---net(三)
- vue watch监听验证码时,axios延迟发送post请求。
- [一]class 文件浅析 .class文件格式详解 字段方法属性常量池字段 class文件属性表 数据类型 数据结构
- mybatis-高级结果映射之一对多
- zabbix3.4安转
- MyCat不适用场景(使用时避免)
- 第三个spring冲刺第4天
- Beanutils工具常用方法
- nrf52832 连接参数更新过程
- Tree Constructing CodeForces - 1003E(构造)