多多的排列函数

[编程题]多多的排列函数

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

数列 {An} 为N的一种排列。

例如N=3，可能的排列共6种：

1, 2, 3``1, 3, 2``2, 1, 3``2, 3, 1``3, 1, 2``3, 2, 1

定义函数F:

其中|X|表示X的绝对值。

现在多多鸡想知道，在所有可能的数列 {An} 中，F(N)的最小值和最大值分别是多少。

输入描述:

第一行输入1个整数T，表示测试用例的组数。
( 1 <= T <= 10 )
第二行开始，共T行，每行包含1个整数N，表示数列 {An} 的元素个数。
( 1 <= N <= 100,000 )

输出描述:

共T行，每行2个整数，分别表示F(N)最小值和最大值

输入例子1:

2
2
3

输出例子1:

1 1
0 2

例子说明1:

对于N=3：
- 当{An}为3，2，1时可以得到F(N)的最小值0
- 当{An}为2，1，3时可以得到F(N)的最大值2

动态规划

dpMax[j] = j - dpMin[j - 1];
dpMin[j] = dpMin[j - 4];

import java.util.*;

public class PDDT2 {


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();

            int[] dpMin = new int[val + 1];
            int[] dpMax = new int[val + 1];
            if (val == 1) {
                System.out.println(1 + " " + 1);
                continue;
            } else if (val == 2) {
                System.out.println(1 + " " + 1);
                continue;
            } else if (val == 3) {
                System.out.println(0 + " " + 2);
                continue;
            } else if (val == 4) {
                System.out.println(0 + " " + 4);
                continue;
            }
            if (val > 4) {
                dpMin[1] = 1;
                dpMin[2] = 1;
                dpMin[3] = 0;
                dpMin[4] = 0;

                dpMax[1] = 1;
                dpMax[2] = 1;
                dpMax[3] = 2;
                dpMax[4] = 4;
                
                for (int j = 5; j <= val; j++) {
                    dpMax[j] = j - dpMin[j - 1];
                    dpMin[j] = dpMin[j - 4];
                }

                System.out.println(dpMin[val] + " " + dpMax[val]);
            }
        }
    }
}

赏

谢谢你请我吃糖果

微信