第一题
找规律,跟leetcode上的一道题比较相似,题号记不清了....
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int digit = 1; int i = 3; String res = ""; while(n-i > 0) { n -= i; i*=3; digit++; } while(digit>0) { int count = (int)Math.pow(3, digit-1); int num = (n-1)/count; res += num==0? "2":num==1? "3":"5"; n -= (num*count); digit--; } System.out.println(res); }
第二题
倒推dp应该是最优解法,我直接暴力dfs....居然过了
import java.util.*; public class Main { static int max = 0; static int[][] map; public static void main(String[] args) { Scanner sc= new Scanner(System.in); int n = sc.nextInt(); map = new int[n][2 * n-1]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= 2 * i -1; j++) { map[i-1][j-1] = sc.nextInt(); } } dfs(0,0,0,n); System.out.println(max); } private static void dfs(int i, int j, int sum,int n) { if(i == n) max = Math.max(max,sum); else{ for(int k = 0; k < 3; k++) { dfs(i+1,j+k,sum + map[i][j],n); } } } }
全部评论
(4) 回帖