3.14IT统一校招笔试题（个人）

3.14的IT春招

第三题的动态规划后面才想出来，不知道能不能过

package 蓝桥杯;

import java.util.Scanner;

/*

• 一条项链 有n个宝珠组成，每个宝珠的数量>=min,<=max
• 求宝珠数量和为m的方案总数
• 动态规划
• 如果dp[j][i]存在那么在加一种宝珠其数量在min和max之间
• 那么dp[]j+1][i+min]到dp[j+1][i+max]都包含dp[j][i]方案总数
• 依次累加
• 注意设定初始值

• */
  public class 动态规划宝珠方案总数 {
  public static void main(String[] args) {

  Scanner in = new Scanner(System.in);
   while (in.hasNext()) {
       int n = in.nextInt();
       int m = in.nextInt();
       int[][] dp = new int[n + 1][m + 1];
       int max[] = new int[n + 1];
       int min[] = new int[n + 1];
       for (int i = 0; i < n; i++) {
           min[i + 1] = in.nextInt();
           max[i + 1] = in.nextInt();
       }
       for (int i = min[1]; i <= max[1]; i++) {
           dp[1][i] = 1;
       }
       for (int j = 1; j < n; j++) {
           for (int i = 0; (i <= m) && (dp[j][i] != 0); i++) {
  
               for (int add = min[j]; (add <= max[j]) && (i + add <= m); add++) {
                   dp[j + 1][i + add] += dp[j][i];
  
               }
  
           }
  
       }
       System.out.println(dp[n][m]);
   }

  }

}
第二题90%，没过，第一题应该是求最小连通子图，暂时没有易于实现的方法