結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 2018-10-17 12:39:21 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 155 ms / 5,000 ms |
コード長 | 888 bytes |
コンパイル時間 | 2,173 ms |
コンパイル使用メモリ | 77,860 KB |
実行使用メモリ | 42,088 KB |
最終ジャッジ日時 | 2024-07-01 09:09:45 |
合計ジャッジ時間 | 8,039 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import java.util.Arrays; import java.util.Scanner; public class Main { @SuppressWarnings("resource") public static void main(String args[]) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); dp = new int[n + 1]; Arrays.fill(dp, 100000000); dp[1] = 1; dfs(1,n); if(dp[n]==100000000) { System.out.println(-1); return; } System.out.println(dp[n]); } static int dp[]; private static void dfs(int i,int n) { if(i==n) { return; } int cnt=cntOnes(i); if (i + cnt <= n) { if(dp[i]+1<dp[i+cnt]) { dp[i+cnt]=Math.min(dp[i]+1, dp[i+cnt]); dfs(i+cnt,n); } } if (i - cnt >= 1) { if(dp[i]+1<dp[i-cnt]) { dp[i-cnt]=Math.min(dp[i]+1, dp[i-cnt]); dfs(i-cnt,n); } } } static private int cntOnes(int n) { int cnt = 0; for (int i = n; i > 0; i /= 2) { if (i % 2 == 1) cnt++; } return cnt; } }