阿里巴巴笔试 3.17

第一题

t组数据

n副牌每副m张求每一组选一张，使得和为k，有多少种情况？

第二题---这个代码过70%

n个零件 m个冲突

每一个零件有对应的时间空间优化a[i],b[i]

m个冲突关系，使得零件之间不能一起选

求，每个零件和其他所有零件组合的开销的总最小值。

5 3
-1 3
2 4
1 1
3 5
2 2
1 4
2 3
3 5
4 14 4 16 10

 / 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    //    static int ans = 0;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        List<Integer> res = new ArrayList<>();
        for(int i=0;i<T;i++){
            int n = cin.nextInt();
            int m = cin.nextInt();
            int k = cin.nextInt();
//            get_ans(n, m, k);
            res.add(get_ans(n, m, k));
        }
        for (int i=0;i<T;i++){
            System.out.println(res.get(i));
        }
    }
    public static int get_ans(int n, int m, int k){
        int res = 0;
        long [][]dp = new long[n+1][k+1];
        for(int j=1;j<=m && j<=k;j++){
            dp[1][j] = 1;
//            System.out.println(1 + " " + j + " " + dp[1][j]);
        }
        for(int i=2;i<=n;i++){
            for(int j=i;j<=k;j++){
                for(int c = 1;c<=m;c++){
                    if(j - c < 1)
                        break;
                    dp[i][j] += dp[i-1][j-c];
//                    System.out.println(i + " " + j + " " + dp[i][j]);
                }
            }
        }
        return (int)(dp[n][k] % 1000000007);
    }
// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
import java.util.*;

public class Main {
//    static int ans = 0;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        List<Integer> lint = new ArrayList<>();
        int []a = new int[n+1];
        int []b = new int[n+1];
        for(int i=1;i<=n;i++){
            a[i] = cin.nextInt();
            b[i] = cin.nextInt();
        }
        char [][]relation = new char[n+1][n+1];
        for (int i=0;i<m;i++){
            int x = cin.nextInt();
            int y = cin.nextInt();
            relation[x][y] = '1';
            relation[y][x] = '1';

        }
        int res;
        for(int i=1;i<=n;i++){
            res = 0;
            for(int j=1;j<=n;j++){
                if (i == j || relation[i][j] == '1')
                    continue;
                res += Math.min(a[i]+b[j], a[j] + b[i]);
            }
            lint.add(res);
        }
        for (int i=0;i<lint.size();i++){
            System.out.print(lint.get(i) + " ");
        }
    }
}

#笔经##阿里巴巴##Java#