fork download 
  1. /*
  2. プログラミングのお題スレ Part12 
  3. ttps://mevius.5ch.net/test/read.cgi/tech/1538096947/613
  4.  
  5. 613 名前：デフォルトの名無しさん[sage] 投稿日：2018/11/21(水) 21:02:48.05 ID:fvygYhm9
  6. お題
  7. 以下の操作を好きなだけ行う時、0をXにするまでに必要な最小コストを求めよ
  8. ・コスト1で値を1増減させる
  9. ・コストn+Yで値をn倍する
  10. XとYは与えられ、0以上の整数であることが保証される
  11. nは自然数の範囲で任意に決めて良い
  12. 例(X, Y)
  13. 1 3
  14. 20 2
  15. 63 2
  16. 出力
  17. 3
  18. 11
  19. 17
  20. */
  21. class Ideone
  22. {
  23.     public static void main(String[] args)
  24.     {
  25.         System.out.println(calc(1, 3));
  26.         System.out.println(calc(20, 2));
  27.         System.out.println(calc(63, 2));
  28.     }
  29.  
  30.     static int calc(int x, int y)
  31.     {
  32.         int[] table = new int[x + 1];
  33.         for (int i = 1; i <= x; i++)
  34.             table[i] = i;
  35.  
  36.         for (int i = 1; i <= x; i++)
  37.         {
  38.             if (table[i - 1] + 1 < table[i]) table[i] = table[i - 1] + 1;
  39.             for (int m = 2; i * m <= x; m++)
  40.             {
  41.                 if (table[i] + m + y < table[i * m])
  42.                 {
  43.                     table[i * m] = table[i] + m + y;
  44.                 }
  45.             }
  46.         }
  47.  
  48.         return table[x];
  49.     }
  50. }
Success #stdin #stdout 0.04s 2184192KB
comments (?)
stdin 
Standard input is empty
stdout 
1
11
17
https://ideone.com/g0xX7G
お題スレ12の613
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!