1. ホーム
  2. Algorithm

その他 - 等差数列はいくつあるか?(ジャワ)

2022-02-22 21:04:05

タイトル要件

入力例

2 7 4 5 6
3 3 3 3 3 3

サンプル出力

12
26

シナリオ1: ダイナミック・プランニング

言語環境。Java - OpenJDK 1.7.0

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String line;
        while (scan.hasNextLine()) {
            line = scan.nextLine().trim();
			Main.solution(line.split(" "));
        }
    }
    
    public static void solution(String[] lineStrArr) {
        int[] lineIntArr = new int[lineStrArr.length];
        int[][] dp = new int[201][401];
        for(int i=0;i<lineStrArr.length;i++){
            lineIntArr[i]=Integer.parseInt(lineStrArr[i]);
        }
        int sum = 0;

        for(int k = -200; k <= 200 ; k++)
        {
            for(int i = lineIntArr.length-1 ; i > 0 ; i--)
            {
                for(int j = i-1 ; j >= 0 ; j--)
                {
                    if(lineIntArr[j] + k == lineIntArr[i])
                    {
                        dp[j][k+200] += dp[i][k+200] + 1;
                    }
                }
            }
        }
        for(int i = 0; i < lineIntArr.length; i++)
        {
            for(int k = 0 ; k <= 400 ; k++)
            {
                sum += dp[i][k];
            }
        }
        System.out.println(sum);
    }
}