fork(1) 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(3, 1));
  27.         System.out.println(calc(20, 2));
  28.         System.out.println(calc(63, 2));
  29.     }
  30.  
  31.     static int calc(int x, int y)
  32.     {
  33.         int[] table = new int[x + 1];
  34.         for (int i = 1; i <= x; i++)
  35.             table[i] = i;
  36.  
  37.         for (int i = 1; i <= x; i++)
  38.         {
  39.             if (table[i - 1] + 1 < table[i]) table[i] = table[i - 1] + 1;
  40.             int m = 2;
  41.             for (; i * m < x; m++)
  42.             {
  43.                 int cost = table[i] + m + y;
  44.                 for (int j = 0; cost + j < table[i * m - j]; j++)
  45.                 {
  46.                     table[i * m - j] = cost + j;
  47.                 }
  48.             }
  49.  
  50.             int cost = table[i] + m + y + i * m - x;
  51.             if (cost < table[x]) table[x] = cost;
  52.         }
  53.  
  54.         return table[x];
  55.     }
  56. }
Success #stdin #stdout 0.04s 2184192KB
comments (?)
stdin 
Standard input is empty
stdout 
1
3
11
17
https://ideone.com/Wmb9ZO
お題スレ12の613
ttps://ideone.com/g0xX7G の修正版
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!