DAY2 LeetCodeACwing

自律刷题DAY2

1、LeetCode693 交替位二进制数

每日打卡题目：每次比较当前位的二进制数和下一位的二级制数，每次循环右移一位。

class Solution {
    public boolean hasAlternatingBits(int n) {
    while(n!=0){
    int x1 = n&1; // 取当前位的数int x2 = n>>1&1; // 取下一位if (x1==x2)  return false;n=n>>1;}return true;}
}

ACwing 1015 摘花生

第（i ， j） 个点 的最大值由 前（i-1 ，j） 和 （i，j-1） 转移而来

w[i] [j] 为矩阵中存储的权值

状态转移方程：
$$f[i][j]=Math.max(f[i][j],Math.max(f[i?1][j],f[i][j?1])+w[i][j]);$$

import java.util.*;
public class Main{
    static int N = 105;static int[][] g = new int[N][N];public static void main(String[] args){
    Scanner in = new Scanner(System.in);int t = in.nextInt();while(t-->0){
    int[][] f =  new int[N][N];int r = in.nextInt();int c = in.nextInt();for(int i = 1 ; i <= r ; i++){
    for(int j = 1 ; j<= c ;j++){
    g[i][j] = in.nextInt();}}for(int i = 1; i <= r ; i++){
    for(int j = 1 ; j <= c ;j++){
    f[i][j] = Math.max(f[i][j] ,Math.max( f[i-1][j] , f[i][j-1])+g[i][j]);}}System.out.println(f[r][c]);}}
}

ACwing 1018 最低通行费

该题思路与上题思路相似

**状态转移方程： **w[i] [j]为权值
$$f[i][j]=Math.min(f[i?1][j],f[i][j?1])+w[i][j];$$

import java.util.*;
public class Main{
    static int N = 105;static int[][] g = new int[N][N];static int[][] f =  new int[N][N];public static void main(String[] args){
    Scanner in = new Scanner(System.in);int n = in.nextInt();for(int i = 0 ; i <= n ; i++){
    for(int j = 0 ; j<= n ;j++){
    if(i>0 && j > 0 ) g[i][j] = in.nextInt();if(i==0 || j == 0) f[i][j] = 0x3f3f3f3f;}}f[1][0] = 0;f[0][1] = 0;for(int i = 1 ; i <= n ; i++){
    for(int j = 1 ; j <= n  ;j++){
    f[i][j] = Math.min(f[i-1][j] , f[i][j-1])+g[i][j];}}System.out.println(f[n][n]);}
}

ACwing1027 方格取数

**状态为f[k] [i1] [i2] : k为第几步，i1为第一次走的 行数 ， i2 为第二次走的 行数。 **

可以不用再开两维用来表示【j1】【j2】

直接用k-i1 , k-i2用来表示j1 ， j2.

考虑第一次走的下一步是否与第二次走的下一步是否相同，相同则只加一次w【i1】【j1】

不同则分别加上w【i1】【j1】，w【i2】【j2】

状态转移方程：
$$f[k?1][i1?1][i2?1]+s:第一步，第二步都往右走$$

$$f[k?1][i1?1][i2]+s:第一步往右走，第二步往下走$$

$$f[k?1][i1][i2]+s：第一步，第二步都往下走$$

$$f[k?1][i1][i2?1]+s：第一步往下走，第二步往右走$$

s 为 当前步 需要加的权值
$$f[k][i1][i2]=max(f[k][i1][i2],f[k?1][i1?1][i2]+s,f[k?1][i1][i2]+s,f[k?1][i1][i2?1]+s,f[k?1][i1?1][i2?1]+s);$$

import java.util.*;
public class Main{
    static int N = 11;static int[][] g = new int[N][N];static int[][][] f =  new int[2*N][N][N];public static void main(String[] args){
    Scanner in = new Scanner(System.in);int n = in.nextInt();while(true){
    int x = in.nextInt();int y = in.nextInt();if(x == 0 && y ==0) break;g[x][y] = in.nextInt();}for(int k = 2 ; k <= 2*n ; k++){
    for(int i1 = 1 ; i1 <= n ; i1++){
    for(int i2 = 1 ; i2 <= n ; i2++){
    int j1 = k - i1;int j2 = k - i2;// System.out.println(j1 + " " + j2);if(j1>=1&&j1<=n&&j2>=1&&j2<=n) {
    int s = g[i1][j1] ;if(i1!=i2){
    s += g[i2][j2];}f[k][i1][i2] = Math.max(f[k][i1][i2],f[k-1][i1-1][i2]+s);f[k][i1][i2] = Math.max(f[k][i1][i2],f[k-1][i1][i2]+s);f[k][i1][i2] = Math.max(f[k][i1][i2],f[k-1][i1][i2-1]+s);f[k][i1][i2] = Math.max(f[k][i1][i2],f[k-1][i1-1][i2-1]+s);}}}}System.out.println(f[2*n][n][n]);}
}

又是废物的一天