C++分析研究  
C++
日历
<2014年3月>
2324252627281
2345678
9101112131415
16171819202122
23242526272829
303112345
统计
  • 随笔 - 92
  • 文章 - 4
  • 评论 - 4
  • 引用 - 0

导航

常用链接

留言簿

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 

  题目描述:
  给从左至右排好队的小朋友们分糖果,
  要求:
  1.每个小朋友都有一个得分,任意两个相邻的小朋友,得分较高的所得的糖果必须大于得分较低的,相等则不作要求。
  2.每个小朋友至少获得一个糖果。
  求,至少需要的糖果数。
  输入:
  输入包含多组测试数据,每组测试数据由一个整数n(1<=n<=100000)开头,接下去一行包含n个整数,代表每个小朋友的分数Si(1<=Si<=10000)。
  输出:
  对于每组测试数据,输出一个整数,代表至少需要的糖果数。
  样例输入:
  3
  1 10 1
  3
  6 2 3
  2
  1 1样例输出:
  4
  5
  2这题可以把所有的人看成图中的一个点,两个相邻的人如果s的值不一样的话可以从大的往小的连一条边,可以很明显的看出,这些人与这些边构成了有向无环图。那么所有人的最小能分配到的糖果值就可以通过他的左右两个人计算出来。可以采用记忆化搜索算法。复杂度是O(n) www.lefeng123.com
  AC代码: #include
  #include
  #include
  #define MAX 100001
  using namespace std;
  int cal(int r,int n,int dp[],int A[])
  {
  if(dp[r]>0)
  return dp[r];//已经计算过
  dp[r]=1;
  if(r+1<=n&&A[r]>A[r+1])//右边有人比他小,要受右边限制
  dp[r]=max(dp[r],cal(r+1,n,dp,A)+1);
  if(r-1>=1&&A[r]>A[r-1])//左边有人比他小,要受左边限制
  dp[r]=max(dp[r],cal(r-1,n,dp,A)+1);
  return dp[r];
  }
  int main(int argc,char *argv[])
  {
  int n;
  int A[MAX];
  int dp[MAX];
  while(scanf("%d",&n)!=EOF)
  {
  int i;
  memset(dp,0,sizeof(dp));
  for(i=1;i<=n;i++)
  scanf("%d",&A[i]);
  long long sum=0;
  for(i=1;i<=n;i++)
  sum+=cal(i,n,dp,A);
  printf("%lld\n",sum);
  }
  return 0;
  }

posted on 2014-03-21 21:26 HAOSOLA 阅读(567) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © HAOSOLA Powered by: 博客园 模板提供:沪江博客
PK10开奖 PK10开奖