java 牛客网之[动态规划 简单]NC4 【模板】前缀和

题目的链接在这里：https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf

• 题目大意
• 一、示意图
• 二、解题思路
• • 超时代码
  • 动态规划 前缀和

超时代码 动态规划 前缀和 sum[i]-sum[j-1]

代码如下：

import java.util.*;

public class  Main{
    public static void main(String[] args) {
         //长度为n的数组 q次查询 查询有l r这两个参数 每次都是输出 al+....+ar
        // 第一行有n和q 第二行有n个正数 然后q行 每行有l和 r ，然后输出q行数据
        //nextInt的结束标记就是  回车 或者空格
        //而nextLine的结束标记 只有回车一个
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int q=sc.nextInt();
        sc.nextLine();
        String[] s=sc.nextLine().split(" ");
        long[] num=new long[n];
        for(int i=0;i0){
            res=0;
            q--;
            //然后进行判定
            int l=sc.nextInt();
            int r=sc.nextInt();
            //再经常消除
            sc.nextLine();
            //这才开始消除
            //直接暴力不好吧
            for(int i=l-1;i<=r-1;i++){
                res+=num[i];
            }
            System.out.println(res);
        }

    }
}

代码如下：

import java.util.*;

import java.util.*;

public class  Main{
  public static void main(String[] args) {
         //长度为n的数组 q次查询 查询有l r这两个参数 每次都是输出 al+....+ar
        // 第一行有n和q 第二行有n个正数 然后q行 每行有l和 r ，然后输出q行数据
        //nextInt的结束标记就是  回车 或者空格
        //而nextLine的结束标记 只有回车一个
        
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //输入的q太长了
        long q=sc.nextLong();
        sc.nextLine();
        //可能是这一步除了问题
        //String[] s=sc.nextLine().split(" ");
        long[] num=new long[n];
        long[] sum=new long[n+1];
        for(int i=0;i0){
            q--;
            int l=sc.nextInt();
            int r=sc.nextInt();
            //然后消除
            sc.nextLine();
            //然后进行判断
            //sum[i] 等于a1+ai+1 所以 sum[l]=a1+..al+1   sum[r]=a1+...ar+1  需要求 al+...ar 那就是sum[r-1]-sum[l-2]吧
            if(l-2<0){
                System.out.println(sum[r-1]-0);
            }
            else
            {
                System.out.println(sum[r - 1] - sum[l - 2]);
            }
        }

  }
}