柳暗花明 2013-08-03 00:30:00
点我顶贴
收藏
删除
本人新手,分不多,望各位见谅。
贴代码:
用的动态规划,提交后状态一直为Run,都40分钟了,木有办法啊,是死循环了么,要提交新的代码也不行了。
/*
* http://www.rqnoj.cn/Problem_167.html
* 题目:免费午餐
* 完成时间:10min
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int longest_decreasing(int* array,int n)
{
int i,j,k=0;
int lenth[n];
for(i=0;i<n;i++)
{
lenth[i] = 1;
for(j=0;j<i;j++)
if(array[i] < array[j] && lenth[j]+1 > lenth[i])
lenth[i] = lenth[j] + 1;
}
for(i=0;i<n;i++)
{
if(lenth[i] > k) k = lenth[i];
}
return k;
}
void main()
{
int i,j,k;
int n;
int array[100000];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&array[i]);
printf("%d",longest_decreasing(&array[0],n));
return;
}
#3 absi2011@2013-08-03 00:30:00
30557
回复
删除
回复 板凳柳暗花明 的帖子
n^2是超时的算法啊。。。。n=100000呢
最长下降子序列有个nlogn的做法,可以百度一下,不是太难(也不是很简单)