好看序列

发表于 更新于 分类于 阅读次数：

Sxdxfz-OJ 1003: 好看序列 看到难度标着基础就去做了，结果思考了很久…… 第一反应暴力，然而一看范围，最多2000个数字（（
想到可以每添加一个数字处理一次，于是研究O(n)算法 一开始的思路是分情况讨论，对于每个新输入的数字判断是否与之前相等之类
然而打了很久的表只拿了9%的分。。。。 转变思路，思考每一个新加入的数字与之前的关系，记录每个数字结尾共有多少种方法 一共有sum种方案，数字n结尾有a[n]种方案
新加入数字n后，a[n]的值=之前不以n结尾方案+之前以n结尾+单独n存在的方案（1）
即新加入后，a[n]=sum+1 于是有了下面的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define rint register int
using namespace std;
inline int read(){
    rint a=1,b=0;char c;
    do{c=getchar();if(c=='-')a=-1;}while(c>'9'c<'0');
    do{b=b*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
    return a*b;
}

int a[50000+10];

int main(){
    rint T,n,tmp,sum=0;
    T=read();
    while(T--){
        n=read();
        tmp=a[n];
        a[n]=sum+1;
        sum=sum-tmp+a[n];
        a[n]=a[n]>1000000007
        ?a[n]%1000000007
        :a[n];
        sum=sum<0
        ?sum+1000000007
        :sum>1000000007
            ?sum%1000000007
            :sum;
    }
    printf("%d",sum);
    return 0;
}