我又又又来问问题了！

常规
1

题目描述

时间：1s 空间：256M

题目描述：

小明爱好音乐，他找了很多杯子在里面接了一些水，这样就能演奏出不同的声音了。

有一天，数学老师看到的这个有趣的现象，向小明提出了一些问题，每次询问一段连续区间杯子里的水，如果倒到一起会有多少？

小明想在数学老师面前表现下，希望用最快的时间回答数学老师，但是他不知道该怎么做，只好来请教你。

输入格式：

第一行一个整数n，表示杯子的总数。

接下来一行n个整数，依序表示每个杯子的蓄水量。

接下来一行一个整数m，表示询问次数。

接下来m行每行两个整数l，r，表示询问区间，询问从第l个杯子到第r个杯子的蓄水量和。

输出格式：

共m行，每行一个整数，表示区间和。

样例输入：

3
1 2 3
1
1 3

样例输出：

6

约定：

n,l,r不超过100000，m不超过100000。

提示：

请使用long long

#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],m,ans=0;
int main(){
  	cin>>n;
    for(int i=1;i<=n;i++)
 	{
   	   cin>>a[i];
 	}
 	cin>>m;
   	 int l,r;
 		for(int i=1;i<=m;i++)
 	  	 {
	    	ans=0;
	        cin>>l>>r;
  		    for(int j=l;j<=r;j++)
 	       	{
 	        	 ans=ans+a[j];
 	       	}
   	    cout<<ans;

 	  }
}
3 个赞
2

前缀和？

2 个赞
3

动态规划：

先求出 a_1 到 a_i 的和

for(int i=1;i<=n;i++)
{
    b[i]+=a[i]+b[i-1];
}

区间 l 到 r ，指 a_l 到 a_r ，也就是 b_r-b_{l-1}

for(int i=1;i<=m;i++)
{
    long long l,r;
    cin>>l>>r;
    cout<<b[r]-b[l-1]<<endl;
}

麻烦给个解决方案

1 个赞