# D1

![image-20250324223257143](C:\Users\33882\AppData\Roaming\Typora\typora-user-images\image-20250324223257143.png)

```JAVA
import java.util.Scanner;
zheshi
public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int [][]arr=new int [n+1][n+1];
        int max=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                arr[i][j]=scan.nextInt();
                arr[i][j]=Math.max(arr[i][j]+arr[i-1][j],arr[i][j]+arr[i-1][j-1]);
                max=Math.max(max,arr[i][j]);
            }
        }
        System.out.println(max);
    }

}
```

![image-20250324223214500](C:\Users\33882\AppData\Roaming\Typora\typora-user-images\image-20250324223214500.png)

```JAVA
	import java.util.Arrays;
        import java.util.Scanner;

        public class Main {
            static int  n;
            static int[] arr = new int[10005];
            static int[] dp = new int[10005];
            static int D(int x) {
                if (x == 1) return 1;
                else {
                    for (int i = 2; i * i <= x; i++) {
                        if (x % i == 0) return i;
                    }
                }
                return x;
            }
            public static void main(String[] args) {
                Scanner scan = new Scanner(System.in);
                n = scan.nextInt();
                for (int i = 1; i <= n; i++) arr[i] = scan.nextInt();
                Arrays.fill(dp,Integer.MIN_VALUE);
                dp[1]=arr[1];
                for (int i = 1; i <= n; i++) {
                   int len=D(n-i);
                   for(int j=1;j<=len;j++){
                       dp[j+i]=Math.max(dp[j+i],dp[i]+arr[i+j]);
                   }
                }
                System.out.println(dp[n]);
            }

        }
```



![image-20250324223201421](C:\Users\33882\AppData\Roaming\Typora\typora-user-images\image-20250324223201421.png)

```JAVA
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        while (t-- > 0) {
            int n, a, b, k;
            n = scan.nextInt();
            a = scan.nextInt();
            b = scan.nextInt();
            k = scan.nextInt();
            int[] arr = new int[n + 1];
            int[][] dp = new int[n + 1][n + 1];
            for (int i = 1; i <= n; i++) arr[i] = scan.nextInt();
            for (int v[] : dp) Arrays.fill(v, Integer.MIN_VALUE);
            int ans = 0;
            dp[0][0] = 0;
            for (int i = 1; i <= k; i++) {//k次数
                for (int j = 1; j <= n; j++) {//区间
                    for (int x = a; x <= b; x++) {//每次能跳的范围
                        if (j >= x) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - x] + arr[j]);
                        //关键就在于 J>=X  J表示的是 以后的位置 而x表示的是跳的步数 如果j>=x 那就说明 j-x的位置是可达的
                        //并且这个题目的解法是从后往前推的 因此就不会由产生后继性 所以我们不用考虑后面的了 红红火火恍恍惚惚哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
                    }
                    ans = Math.max(ans, dp[i][j]);
                }
            }
            System.out.println(ans);

        }
    }
}
```

# D2 前缀和&&差分

![image-20250325190257802](C:\Users\33882\AppData\Roaming\Typora\typora-user-images\image-20250325190257802.png)

```java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n= scan.nextInt();
        int m=scan.nextInt();
        int []a=new int [n+1];
        for(int i=1;i<=n;i++){
            a[i]=scan.nextInt();
            a[i]=a[i]+a[i-1];
        }
        for(int i=0;i<m;i++){
            int l=scan.nextInt();
            int r=scan.nextInt();
            System.out.println(a[r]-a[l-1]);
        }
    }

}
```



## 二维前缀和

![image-20250325190329215](C:\Users\33882\AppData\Roaming\Typora\typora-user-images\image-20250325190329215.png)