题解 P1567 【统计天数】

**题目的本质很好理解：求一个序列的最长上升子串** (附：子串指必须是连续的) $ $ $ $ $1.$ **40分算法：** $ $先输入每个数，再枚举每个右端点，每次向左进行扩展，直到不再是上升的，输出扩展出的长度的最大值。 代码（巨丑，将就一下吧）： ```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而已) $ $ ___ $ $ $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}$$ $ $ 给出代码： ```cpp #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分记录](https://www.luogu.org/record/16041092) $ $ ___ $ $ $3.$ **100分算法2** 其实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)： ```cpp #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); } ``` [提交记录](https://www.luogu.org/record/22387793) ___ $ $ Update:2019/8/8,因为码风变化较大，又学到了更多常数优化相关的东西，而且洛谷提交记录界面改变，所以重打了一遍代码，并更新文中链接。同时对其他部分的排版做翻新。 Update:2020/4/7,又用了一些奇怪的优化，代码如下： ```cpp #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); } ``` 请结合此图进行理解：