poj 2385Apple Catching(简单dp)

  1. 云栖社区>
  2. 博客列表>
  3. 正文

poj 2385Apple Catching(简单dp)

hjzgg 2016-04-28 13:35:15 浏览243 评论0

摘要: /* 题意: 有两棵苹果树,每一棵苹果树每一秒间隔的掉落下来一个苹果,一个人在树下接住苹果,不让苹果掉落! 人在两棵树之间的移动是很快的!但是这个人移动的次数是有限制的,问最多可以接住多少个苹果! 思路:dp[i][j]表示的是前 i个苹果掉落之后, 移动次数是j...


/*
    题意: 有两棵苹果树,每一棵苹果树每一秒间隔的掉落下来一个苹果,一个人在树下接住苹果,不让苹果掉落!
    人在两棵树之间的移动是很快的!但是这个人移动的次数是有限制的,问最多可以接住多少个苹果!
    
    思路:dp[i][j]表示的是前 i个苹果掉落之后, 移动次数是j的情况下的最多接住的苹果的个数!
    
    那么dp[i][j]=max(dp[i-1][j], dp[i][j-1]) + a[i]==j%2+1 ? 1 : 0;
    
    a[i]==j%2+1 表明第j次移动恰好移动到 第 a[i]棵苹果树下,此时这棵苹果树这号掉落下了苹果,正好接住! 
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define M 1005
using namespace std;

int dp[M][35];

int n, m;
int a[M];

int main(){
   scanf("%d%d", &n, &m);
   for(int i=1; i<=n; ++i)
      scanf("%d", &a[i]);
   if(a[1]==1) dp[1][0]+=1;
   for(int i=2; i<=n; ++i){
       dp[i][0]=dp[i-1][0];
       if(a[i]==1)
          dp[i][0]+=1;
   }
      
   for(int j=1; j<=m; ++j)
      for(int i=j; i<=n; ++i){
             dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
           int cc=j%2+1;
           if(a[i]==cc)
              dp[i][j]+=1;
      } 
   printf("%d\n", dp[n][m]);
   return 0;
}

用云栖社区APP,舒服~

【云栖快讯】新年大招!云栖社区为在读大学生/研究生准备了一份学(huan)习(zhuang)攻略,发布博文即有机会赢得iPad mini 4等大奖,学习换装两不误!欢迎报名参与~  详情请点击

网友评论

hjzgg
文章323篇 | 关注9
关注
是一款简单高效的电子邮件发送服务,它构建在可靠稳定的阿里云基础之上,帮助您快速、精准地实现事... 查看详情
是解决用户结构化数据搜索需求的托管服务,支持数据结构、搜索排序、数据处理自由定制。 为您的网... 查看详情
是一种简单易用的云计算资源管理和自动化运维服务。用户通过模板描述多个云计算资源的依赖关系、配... 查看详情
2017阿里千余份技术干货大盘点

2017阿里千余份技术干货大盘点