首页 > 代码库 > URAL 1044 Lucky Tickets. Easy!

URAL 1044 Lucky Tickets. Easy!

算是个动态规划,统计和

sum[位数][差值]

构建个虚拟数组写起来就顺多了

 1 import java.util.Scanner; 2  3 public class P1044 4 { 5     private static int save[][] = new int[10][100]; 6  7     private static int getSum(int n, int deta) 8     { 9         return save[n][deta + 50];10     }11 12     private static void addSum(int n, int deta, int sum)13     {14         save[n][deta + 50] += sum;15     }16 17     public static void main(String args[])18     {19         addSum(0, 0, 1);20         for (int i = 0; i <= 6; i++)21             for (int deta = -36; deta <= 36; deta++)22                 if (getSum(i, deta) != 0)23                     for (int x = 0; x <= 9; x++)24                         for (int y = 0; y <= 9; y++)25                             addSum(i + 2, deta + x - y, getSum(i, deta));26         try (Scanner cin = new Scanner(System.in))27         {28             while (cin.hasNext())29             {30                 int n = cin.nextInt();31                 System.out.println(getSum(n, 0));32             }33         }34     }35 }

 

URAL 1044 Lucky Tickets. Easy!