poj2385 简单DP

时间：2021-12-29 03:04:11
J - 简单dp

Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

It is a little known fact that cows love apples. Farmer John has two apple trees (which are conveniently numbered 1 and 2) in his field, each full of apples. Bessie cannot reach the apples when they are on the tree, so she must wait for them to fall. However, she must catch them in the air since the apples bruise when they hit the ground (and no one wants to eat bruised apples). Bessie is a quick eater, so an apple she does catch is eaten in just a few seconds.

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

* Line 1: Two space separated integers: T and W

* Lines 2..T+1: 1 or 2: the tree that will drop an apple each minute.

Output

* Line 1: The maximum number of apples Bessie can catch without walking more than W times.

Sample Input

7 2

2

1

1

2

2

1

1

Sample Output

6

Hint

INPUT DETAILS:

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.

题目大意：有两课苹果树，编号为1和2，每一分钟都会有苹果从其中之一落下，刚开始的时候人在苹果树1的下面，这个人最多可以移动w
次,问最终这个人最多可以拿到多少苹果。
思路分析：本问题中，总共有三个变量，一个是当前是第几分钟（i)，另一个是已经移动了多少次(j)，除此之外，还有这个人当前处在哪一棵苹果树
下，但是我们发现，这个人当前在哪一棵苹果树是可以通过移动的次数推算出来的，也就是说现在的变量只有i,j,我们最后要求的就是dp[T][j]的最大值
同时决策就是在当前分钟要不要移动，决策就会引起状态的转移，dp[i][j]=max(dp[i-1][j]，dp[i-1][j-1]),同时对每一步要进行判断，如果当前所在的
苹果树在i分钟刚好掉落苹果，那么dp[i][j]++;
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
const int maxn1=1000+10;
const int maxn2=30+5;
int dp[maxn1][maxn2];//dp[i][j]代表的是前imin，移动j次可以捡到的最大苹果数
int num[maxn1];
const int inf=0xffffff;
int main()
{
     int t,w;
     while(scanf("%d%d",&t,&w)!=EOF)
     {
         memset(dp,0,sizeof(dp));
        for(int i=1;i<=t;i++)
            scanf("%d",&num[i]);
        if(num[1]==1) dp[1][0]=1,dp[1][1]=0;
        else dp[1][0]=0,dp[1][1]=1;
        for(int i=2;i<=t;i++)
        {
            for(int j=0;j<=w;j++)
            {
                if(j==0) dp[i][j]=dp[i-1][j]+(num[i]==1);
                else
                {
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
                    if(j%2+1==num[i]) dp[i][j]++;
                }
            }
        }
        int ma=-inf;
            for(int j=0;j<=w;j++)
            if(dp[t][j]>ma) ma=dp[t][j];
        cout<<ma<<endl;
     }
    return 0;
}

随机推荐

  1. c&num;程序中对密码进行加密的方法

    在ADO.NET中,向数据库添加数据时,怎样对数据中的密码进行加密?(也就是说在数据表中也看不到用户的密 码,只是一些经过编译后的字符串,以防止数据库管理员利用用户的密码进行非法操作.)    首先, ...

  2. php 类编写

    1.没有重载的函数,实现重载函数只能通过func_get_args()这种方式进行转化 2.每个变量只能单独命名为控制权限(private.protected.public) 3.php反射类带参数 ...

  3. &ldquo&semi;锁定&rdquo&semi;语句 lock（C&num; 参考）

    此文章由人工翻译. 将光标移到文章的句子上,以查看原文. 更多信息. 译文 原文 "锁定"语句(C# 参考) 其他版本 <?XML:NAMESPACE PREFIX = &q ...

  4. WCF消息

    1. MessageContract 序列化一个对象并生成消息的时候,希望将部分数据成员作为SOAP的报头,部分作为消息的主体.比如说,我们有一个服务操作采用流的方式进行文件的上载,除了以流的方式传输 ...

  5. TOGAF架构开发方法（ADM）之迁移规划阶段

    TOGAF架构开发方法(ADM)之迁移规划阶段 1.8 迁移规划(Migration Planning) 企业架构开发方法各阶段——迁移规划 1.8.1 目标 本阶段的目标是: 确保实施和迁移规划与企 ...

  6. photo

    我们在android开发过程中 经常有做到发图片或修改上传头像的功能 即要调用系统相册 如何调用系统相册并处理返回的数据呢?因为随着android手机系统的提高 不同系统的手机对调用相册并处理相册不同 ...

  7. 使用supervisor 进行进程管理时调整最大文件打开数

    [supervisord]logfile=/tmp/supervisord.log ; 日志文件,默认是 $CWD/supervisord.loglogfile_maxbytes=50MB ; 日志文 ...

  8. 2018-09-15 Java源码英翻中库以及服务原型

    服务很简单, 只为演示这个库, 源码在: program-in-chinese/code_translator_service. 在Postman测试效果: 演示服务地址: 74.91.17.250: ...

  9. CF1120D（神奇的构造&plus;最小生成树）

    考虑把树展开,单独把叶子节点拿出来 于是可以把控制点\(x\)的,抽象成是在它叶子节点间连权值为\(c_x\)的边 显然只用在\(x\)子树的最左边的叶子节点和最右边的叶子节点的下一个节点连边(最后一 ...

  10. element-ui 的el-button组件中添加自定义颜色和图标

    我使用的element-ui的版本是V1.4.13. 如上图所示,如果使用el-button,加颜色是可以通过设置type属性的值,加图标就设置icon属性的值. 现在产品给了一个需求,就是自定义的很 ...

相关文章