美团笔试-小美的元素删除

小美的元素删除

小美有一个数组，她希望删除k个元素，使得剩余的元素两两之间互为倍数关系。你能告诉小美有多少种删除方案吗？

由于答案过大，请对10^9+7模。

输入描述

第一行输入两个整数n,k(1<=k<=n<=10^3)表示数组长度，删除的元素数量。

第二行输入n,k个整数表示数组a(1<=ai<=10^9)。

保证给定的数组中不存在两个相等元素。

输出描述

输出一个整数表示答案。

示例1

输入

6 4
1 4 2 3 6 7

输出

8

说明

方案1：删除1,4,2,7。

方案2：删除1,4,3,7。

方案3：删除1,3,6,7。

方案4：删除4,2,3,6。

方案5：删除4,2,3,7。

方案6：删除4,2,6,7。

方案7：删除4,3,6,7。

方案8：删除2,3,6,7。

思路

我们先将所有的数从小到大进行排序，再记录每一个数的约数的索引

接着定义dp数组 ：dp[i][j] = 为以i为结尾的，长度为j的数组中可以相约的数的数量

我们可以得到状态转移方程： dp[i][j] = 所有的dp[p][j-1]之和（p为i的约数）

最后我们累加 dp[i][n-k]即可。

代码

import java.util.*;

public class test {
    static final int MAXN = 1005;
    static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int keep = n-k;

        int[] a = new int[MAXN];
        for(int i = 1 ;i<=n;i++){
            a[i] = scanner.nextInt();
        }

        Arrays.sort(a,1,n+1);
        List<Integer>[] yueshu = new ArrayList[MAXN];
        for(int i=1;i<=n;i++){
            yueshu[i] = new ArrayList<>();
        }

        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){
                if(a[i]%a[j] == 0){
                    yueshu[i].add(j);
                }
            }
        }

//        定义dp[i][j] = 为以i为结尾的，长度为j的数组中可以相约的数的数量
        long[][] dp = new long[MAXN][MAXN];
        for(int i=1;i<=n;i++){
            dp[i][1] = 1;  //以i为结尾的，长度为1的数组中可以相约的数的数量为1
        }
        for(int i = 1;i<=n;i++){
            for (int j=2;j<=keep;j++){ // keep为需要保存的数字的个数
                for(int p : yueshu[i]){
                    dp[i][j] = dp[p][j-1] + dp[i][j];
                }
            }
        }

        int ans = 0;
        for (int i = 1;i<=n;i++){
            ans = (int) ((ans+dp[i][keep]) % MOD);
        }

        System.out.println(ans);
    }
}