模板大全

0
15

快读:

1 int read () {
2      int k=0,f=1;
3      char c=getchar();
4      while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
5      while (c>='0'||c<='9') {k=k*10+c-'0';c=getchar();}
6      return f*k;
7  }

最长上升序列:

#include <cstdio>
#include <algorithm>
using namespace std;
int n,x,f[1005],len,i;
int main () {
    scanf ("%d",&n);
    for (i=1;i<=n;i++) {
        scanf ("%d",&x);
        if (x>f[len]) 
            f[++len]=x;
        else 
            f[lower_bound(f+1,f+len+1,x)-f]=x;
    }
    printf ("%d\n",len);
    return 0;
} 

最长不降子序列:

#include <cstdio>
#include <algorithm>
using namespace std;
int n,x,f[1005],len,i;
int main () {
    scanf ("%d",&n);
    for (i=1;i<=n;i++) {
        scanf ("%d",&x);
        if (x>=f[len]) 
            f[++len]=x;
        else 
            f[upper_bound(f+1,f+len+1,x)-f]=x;
    }
    printf ("%d\n",len);
    return 0;
} 

<

发布回复

请输入评论!
请输入你的名字