Question

杭电ACM 1257 为什么老是WA？

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
main()
{
int t,l=0,a=0,f,i;
while(~scanf("%d",&t))
{
for(i=1;i<=t;i++)
{
scanf("%d",&f);
if(f>l) a+=1;
l=f;
}
printf("%d\n",a);
a=0;
l=0;
}
}

Answer 1

这道题目是动态规划哈,不是贪心,是求最长递增子序列的.你可一直接百度一下 单调递增子序列或者直接百度 HDU 1257 你这算法肯定不对 所以错了.

这道题要求最长递增子序列的长度，用二分+DP可求的。

#include <iostream>

using namespace std;

int result[30005]; //用于保存最长递增子序列

int bisearch(int a[],int lenth,int h) //二分查找插入的位子，如h存在，则返回原位置，既不做改变，否则返回比h大的位子
{
int i=0,j=lenth-1,mid;
while(i<=j)
{
mid=(i+j)/2;
if(a[mid]==h)
return mid;
if(a[mid]>h)
j=mid-1;
else
i=mid+1;
}
return i;
}

int main()
{
int n,h,lenth,pos;
while(scanf("%d",&n)!=EOF) //注意写上EOF，否则超时
{
result[0]=30005; //初始化最大，第一次执行的是插入操作
lenth=1;
while(n--)
{
scanf("%d",&h);
if(h>result[lenth-1]) //如果h比排头的大，则将h作为新的排头，长度增加，注意是>不是>=，
//如果有=则表示非递减序列，与题意不符
result[lenth++]=h;
else //否则进行插入操作，将比h大一点的数覆盖，不影响结果
{
pos=bisearch(result,lenth,h);
result[pos]=h;
}
}
printf("%d\n",lenth);
}
return 0;
}

Answer 2

好吧~
我直接了当地说~思路错误
给你一组数据
4
3 4 2 3
正确结果应该是3->2，4->3。共2
而你的程序算出来是3

Answer 3

这是一题DP问题不是这么简单的 可以自己百度查一下答案