题解 P1567 【统计天数】

题目的本质很好理解:求一个序列的最长上升子串

(附:子串指必须是连续的)

$ $
$ $
$1.$ 40分算法:

$ $ 先输入每个数,再枚举每个右端点,每次向左进行扩展,直到不再是上升的,输出扩展出的长度的最大值。

代码(巨丑,将就一下吧):

#include<bits/stdc++.h>
using namespace std;
int n,a[10000005];
int main()
{
    cin>>n;
    int ans=1;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2;i<=n;i++)
        {
            int tmp=1;
            for(int j=i-1;j>0;j--)if(a[j]<a[j+1])tmp++;else break;
            if(tmp>ans)ans=tmp;
        }
    cout<<ans;
}

附:60分记录(只不过O2而已)
$ $


$ $
$2.$ 100分算法1

为什么会TLE?

因为每次枚举的时候都会重新扩展一遍,其实每次扩展出的结果可以由上一个数扩展出的结果得出。

这就有点像DP了。(不懂DP的同学可以暂时理解为“类似于递推的东西”。)
状态转移方程:(看不懂的同学请跳过)

$$DP[\,i\,]=\begin{cases}1&\mathtt{i==1\:|\,|\:a\,[\,i-1\,]\geqslant a\,[\,i\,]\,}\\dp\,[\,i-1\,]+1&\mathtt{others}\end{cases}$$

$ $
给出代码:

#include<bits/stdc++.h>
using namespace std;
int n,a[10000005],dp[10000005]={0,1};
int main()
{
    cin>>n;
    int ans=1;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2;i<=n;i++)
        {
            if(a[i]>a[i-1])dp[i]=dp[i-1]+1;
            else dp[i]=1;
            if(dp[i]>ans)ans=dp[i];
        }
    cout<<ans;
}

附:100分记录
$ $


$ $
$3.$ 100分算法2

其实a[]和DP[]也没有必要保存,因为需要的只是a[i-1]和DP[i-1]。 所以可以用两个变量储存,用完重新赋值

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,ans=0,last=0,cur,maxans=0;
    cin>>n;
    while(n--)
        {
            cin>>cur;
            if(cur>last)ans++;
            else ans=1;
            if(ans>maxans)maxans=ans;
            last=cur;
        }
    cout<<maxans;
}

附:100分记录 $ $


$ $
$ $

最后给出一份经过一系列难以理解的神奇优化的代码(97ms):

#include<stdio.h>
inline int read()
{
    register char ch=getchar();
    register int x=0;
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch<='9'&&ch>='0')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
inline void print(int x)
{
//  if(!x){putchar('0');return;}  这一行没有用,因为答案肯定不是0
    register int cnt=0;
    char ch[12];
    while(x)ch[cnt++]=x%10+48,x/=10;
    while(cnt--)putchar(ch[cnt]);
}
int main()
{
    register int n=read(),ans=0,x=0,y,mans=0;
    while(n--)ans=((y=read())>x)?ans+1:1,(ans>mans)&&(mans=ans),x=y;
    print(mans);
}

提交记录
一个更玄学优化的记录,基本上没人看得懂,但很奇怪跑出来反而更慢
$ $
$ $
$ $


$ $
Update:2019/8/8,因为码风变化较大,又学到了更多常数优化相关的东西,而且洛谷提交记录界面改变,所以重打了一遍代码,并更新文中链接。同时对其他部分的排版做翻新。


发表于 2019-01-24 23:54:54 in 题解