首页 > 学院 > 开发设计 > 正文

算法提高 聪明的美食家

2019-11-06 07:35:23
字体:
来源:转载
供稿:网友
  算法提高 聪明的美食家  时间限制:1.0s   内存限制:256.0MB    问题描述  如果有人认为吃东西只需要嘴巴,那就错了。  都知道舌头有这么一个特性,“由简入奢易,由奢如简难”(据好事者考究,此规律也适合许多其他情况)。具体而言,如果是甜食,当你吃的食物不如前面刚吃过的东西甜,就很不爽了。  大宝是一个聪明的美食家,当然深谙此道。一次他来到某小吃一条街,准备从街的一头吃到另一头。为了吃得爽,他大费周章,得到了各种食物的“美味度”。他拒绝不爽的经历,不走回头路而且还要爽歪歪(爽的次数尽量多)。输入格式  两行数据。  第一行为一个整数n,表示小吃街上小吃的数量  第二行为n个整数,分别表示n种食物的“美味度”输出格式  一个整数,表示吃得爽的次数样例输入103 18 7 14 10 12 23 41 16 24样例输出6数据规模和约定  美味度为0到100的整数  n<1000 
源代码1
import java.util.Scanner;2
public class Main { 3
public static void main(String[] args){4
  Scanner sc=new Scanner(System.in);5
  int n=sc.nextInt();6
  int []a=new int[n];7
  int []b=new int[n];8
  for(int i=0;i<n;i++){9
  a[i]=sc.nextInt();10
  }11
  b[0]=1;   12
  int sum=0;13
  for(int i=0;i<n;i++){14
    int max=0;15
    for(int j=i-1;j>=0;j--){16
    if(a[i]>=a[j]){17
      max=Math.max(max,b[j]);18
    }19
    b[i]=max+1;20
    sum=Math.max(sum, b[i]);21
    }22
  }23
  System.out.PRintln(sum);24
}25
}26
分析:求最长不降子序列(http://blog.sina.com.cn/s/blog_6ceb295d0100lzut.html)~用动态规划解决~建立一个与序列等长的数组b~b[i]表示当前i处能够构成的最长不降子序列的长度~所以说当前b[i]的值为前面所有数字比当前i处数字小的长度的最大值+1~最后返回整个b数组中的最大值~~
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表