数组切分

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class 数组切分 {
    static int zu;
    public static void main(String[] args) {
        int t=1;
        for(zu=1;zu<=t;zu++) solve();
        out.flush();
    }
    static int a[]=new int[(int) (1e4+10)];
    static int f[]=new int[(int) (1e4+10)];
    static int mod= (int) (1e9+7);
    static void solve(){
        int n=in.nextInt();
        for(int i=1;i<=n;i++) a[i]=in.nextInt();
        int ma=0,mi=0;
        f[0]=1;
        for(int i=1;i<=n;i++){
            ma=a[i];mi=a[i];
            for(int j=i;j>=1;j--){
                ma=Math.max(a[j],ma);
                mi=Math.min(a[j],mi);
                if(ma-mi+1==i-j+1){
                    f[i]=(f[i]+f[j-1])%mod;
                }
            }
        }
        out.print(f[n]);
    }

    static FastReader in = new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            String str="";
            while(st==null||!st.hasMoreElements()){
                try {
                    str=br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

回忆迷宫

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int zu;
    public static void main(String[] args) {
        int t=1;
        for(zu=1;zu<=t;zu++) solve();
        out.flush();
    }
    static char g[][]=new char[250][250];
    static int dx[]={1,0,-1,0};
    static int dy[]={0,1,0,-1};
    static void solve(){
        for(char v[]:g) Arrays.fill(v,' ');
        int n=in.nextInt();
        String s=in.next();
        int u=110,r=110,d=110,l=110;
        int x=110,y=110;
        g[x][y]='1';
        g[x+1][y]='*';
        g[x-1][y]='*';
        g[x][y+1]='*';
        g[x][y-1]='*';
        for(int i=0;i<n;i++){
            char c=s.charAt(i);
            if(c=='U'){
                x--;
            }else if(c=='D'){
                x++;
            }else if(c=='L'){
                y--;
            }else{
                y++;
            }
            g[x][y]='1';
            for(int k=0;k<4;k++){
                int a=dx[k]+x;
                int b=dy[k]+y;
                if(g[a][b]=='1') continue;
                g[a][b]='*';
            }
            u=Math.min(u,x);
            d=Math.max(d,x);
            l=Math.min(l,y);
            r=Math.max(r,y);
        }
        bfs(0,0);
        u--;
        r++;
        l--;
        d++;
        for(int i=u;i<=d;i++){
            for(int j=l;j<=r;j++){
                if(g[i][j]=='1') out.print(' ');
                else if(g[i][j]=='2') out.print(' ');
                else out.print('*');
            }out.println();
        }
    }
    static void bfs(int x,int y){
        g[x][y]='2';
        Queue<int[]> q=new ArrayDeque<>();
        q.offer(new int[]{x,y});
        while(!q.isEmpty()){
            int []t=q.poll();
            for(int k=0;k<4;k++){
                int a=t[0]+dx[k];
                int b=t[1]+dy[k];
                if(a<0||a>=g.length||b<0||b>=g[0].length) continue;
                if(g[a][b]=='*'||g[a][b]=='2') continue;
                q.offer(new int[]{a,b});
                g[a][b]='2';
            }
        }
    }
    static FastReader in = new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            String str="";
            while(st==null||!st.hasMoreElements()){
                try {
                    str=br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
    }
}