题解 P1567 【统计天数】

· · 题解

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

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

$ $先输入每个数，再枚举每个右端点，每次向左进行扩展，直到不再是上升的，输出扩展出的长度的最大值。 代码（巨丑，将就一下吧）： ```cpp #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分记录](https://www.luogu.org/record/16041151)(只不过O2而已) $ 为什么会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分记录

其实a[]和DP[]也没有必要保存，因为需要的只是a[i-1]和DP[i-1]。 所以**可以用两个变量储存，用完重新赋值** ```cpp #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分记录](https://www.luogu.org/record/16041492) $

最后给出一份经过一系列难以理解的神奇优化的代码(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,因为码风变化较大，又学到了更多常数优化相关的东西，而且洛谷提交记录界面改变，所以重打了一遍代码，并更新文中链接。同时对其他部分的排版做翻新。

Update:2020/4/7,又用了一些奇怪的优化，代码如下：

#include<stdio.h>
const unsigned TOP=1200000;//反复测试出的数据
char T[TOP],*x1(T),*y1(T);
inline char get()
{
    x1==y1&&(y1=(x1=T)+fread(T,1,TOP,stdin));return *x1++;
}
inline unsigned r()
{
    register unsigned x;register char c;
    (c=get())&16?x=c&15:x=get()&15;//钻了输入格式的空子
    while((c=get())&16)x=x*10+(c&15);
    return x;
}
int main()
{
    register unsigned n(r()),a(0),x(0),y,m(0);char ch[6];//注意这个是可以Hack的，当且仅当答案为1e6时会RE。想一想怎么解决
    while(n--)(y=r())>x?++a:((a>m)&&(m=a),a=1),x=y;
    (a>m)&&(m=a);
    register char* c(ch+5);
    while(m)*--c=m%10|48,m/=10;
    fputs(c,stdout);
}

请结合此图进行理解：