注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ1952BUY LOW, BUY LOWER题解  

2014-03-12 22:35:06|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                          低价购物
                                                BY   LGS
题目大意:给你一串数列,求最长不降子序列的长度和个数(完全相同的只算一个)

题解:对于第一问貌似C++系统函数直接1行代码解决,而且是Nlog(N)的。但我还是手写了N方的。算出F[I]对于第二问,仔细思考便能想出思路:首先,如果当前的那个数值的F[I]=F[J]+1(条件1),J<I那么他们一定可以组成一个序列,当前长度、当前位置的总数便是B[I]:许多个满足条件1B[J].写成表达式:B[I]+=B[J];而对于题目里描述的重复问题。我们可以这样想,每次如果推的时候前面有两个相同的加起来一定会重复是吧,而如果我们在前面A[I]=A[J]的时候就把A[J]变成假的,我是赋值成-1的(注意:为什么不是A[i]变-1呢,留给你们思考)。重复问题轻而易举的解决了。

总结:WA了一次,0的时候没考虑。详见代码解析
代码:
#include<cstdio>
#include<cstring>
using namespace std;
int i,j,n,m,k,len,ans;
int a[5001],b[5001],f[5001];
int max(int a,int b){return (a>b)?a:b;}
int main()
{
 scanf("%d",&n);
 for (i=1;i<=n;i++){scanf("%d",&a[i]);f[i]=1;}
 for (i=2;i<=n;i++)
  for (j=1;j<=i-1;j++) if (a[j]>a[i])
            f[i]=max(f[i],f[j]+1);           
len=0;
 for (i=1;i<=n;i++) len=max(len,f[i]);//以上是计算最长不降序列的长度
 
 
 for (i=2;i<=n;i++)
   for (j=1;j<=i-1;j++){
               if (a[j]==a[i])
               {b[j]=-1;continue;}//相等就把B[J]去重。
       if (f[j]+1==f[i]&&a[j]>a[i])
                           {
                          if (!b[j]) b[i]++;//一开始本身就是一种。
                               else if (b[j]!=-1) b[i]+=b[j];//若为-1不能加
                           };
                       }  //以上是计算最长不降的总数。
ans=0;
for (i=1;i<=n;i++) if (f[i]==len&&(b[i]!=-1)) 
                if (b[i]==0) ans++; //上面倒是考虑了,输出时却忘记考虑初始的了,如序列1 2 3.所以第一次交WA2点。
                        else    ans+=b[i];
printf("%d %d",len,ans);
return 0;
}
  评论这张
 
阅读(55)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018