hihocoder57

http://hihocoder.com/contest/offers57/problems
题目1 : 1-偏差排列
DP

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        if(n<=3) {
            System.out.println(n);
            return;
        }
        
        long[]dp=new long[1+n];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++) dp[i]=dp[i-1]+dp[i-2];
        System.out.println(dp[n]);
    }
}

题目2 : 递增N元组
sort+DP

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        int[][]a=new int[n][m];
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++)a[i][j]=sc.nextInt();
            Arrays.sort(a[i]);
        }
        long[][]dp=new long[n][m];
        Arrays.fill(dp[0], 1);
        for(int i=1;i<n;i++) {
            long[]sum=new long[m];
            sum[0] = dp[i-1][0];
            for(int j=1;j<m;j++) sum[j]=sum[j-1]+dp[i-1][j];
            
            for(int j=0;j<m;j++) {
                int t=BS(a[i-1], a[i][j]);
                if(a[i-1][t]>=a[i][j]) continue;
                dp[i][j] = sum[t];
                dp[i][j]%=1000000007;
            }
        }
            
        long s=0;
        for(int j=0;j<m;j++)s+=dp[n-1][j];
        System.out.println(s%1000000007);
    }

    private static int BS(int[] a, int v) {
        int lo=0,hi=a.length-1;
        while(lo+1<hi) {
            int mid=(lo+hi)/2;
            if(a[mid]>=v) hi=mid-1;
            else lo=mid;
        }
        if(lo+1==hi && a[hi]<v) return hi; 
        return lo;
    }
}

题目3 : 逃离迷宫5
BFS+DP

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        char[][]cs=new char[n][n];
        for(int i=0;i<n;i++) cs[i]=sc.next().toCharArray();
        
        int[][][]dp=new int[n][n][2];
        for(int[][]t:dp) for(int[]tt:t) Arrays.fill(tt, 1000009);
        dp[0][0][0] = 0;
        dp[0][0][1] = 0;
//        int step=0;
        int[][]dirs={{1,0},{-1,0},{0,1},{0,-1}};
        
        Queue<int[]>q=new LinkedList<int[]>(); //, qq=new LinkedList<int[]>(), tmp=new LinkedList<int[]>();
        q.add(new int[]{0,0});
        while(!q.isEmpty()) {
            while(!q.isEmpty()) {
                int[]t=q.remove();
                int i=t[0],j=t[1];
                if(i==n-1&&j==n-1) {
                    System.out.println(Math.min(dp[n-1][n-1][0], dp[n-1][n-1][1]));
                    return;
                }
                
                for(int[]d:dirs) {
                    int ii=t[0]+d[0],jj=t[1]+d[1];
                    if(ii<0||jj<0||ii>=n||jj>=n) continue;
                    if(cs[ii][jj]=='.') {
                        if(dp[i][j][0]+1<dp[ii][jj][0] || dp[i][j][1]+1<dp[ii][jj][1]) 
                            q.add(new int[]{ii,jj});
                        dp[ii][jj][0]=Math.min(dp[ii][jj][0], dp[i][j][0]+1);
                        dp[ii][jj][1]=Math.min(dp[ii][jj][1], dp[i][j][1]+1);
                    } else {
                        if(dp[i][j][1]+1<dp[ii][jj][0]) 
                            q.add(new int[]{ii,jj});
                        dp[ii][jj][0]=Math.min(dp[ii][jj][0], dp[i][j][1]+1);
                    }
                }
            }
        }
        
        System.out.println(-1);
    }
}