1107: 迟来的A+B
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1049 Solved: 249
[Submit][Status][Web Board]
Description
“A+B”多么熟悉的题目,在本届校赛开始前CHZ同学（人称“dp小王子“）一直叫我出道A+B给他做，但由于各种原因没有出成，使他感到很遗憾，为了在世界末日前弥补他的遗憾，就决定出道A+B献给CHZ同学！！题目是这样的：
先给你n（1=<n<=100000）个数的数组A，再给你两个数X，Y(1=<X,Y<n)，求sum=(A0+A1+….+Ax-1)+(Ay+Ay+1+….+An-1);
Input
有多组数据，每组数据的第一行有两个数字n，m（1=<m<=100000），表示数据的个数和查询的个数，第二行是n个数据，第三行到m+3行每行有两个数X，Y（1=<X，Y<n）;
Output
对每个查询输出一个结果，每个结果占一行
Sample Input
10 1 1 2 3 4 5 5 4 3 2 1 5 5
Sample Output
30
【分析】
直接做的会会超时，所以把数组分成前后 两个部分来进行求和；
#include <bits/stdc++.h>
using namespace std;
const int maxn=100010;
long long num[maxn]={0},A[maxn]={0},B[maxn]={0};
int main()
{int n,m;int x,y;while(scanf("%d%d",&n,&m)!=EOF){int i;for(i=0;i<n;i++)scanf("%lld",&num[i]);int k;for(k=1;k<=n;k++) A[k]=A[k-1]+num[k-1];for(k=n-1;k>=1;k--) B[k]=B[k+1]+num[k];while(m--){scanf("%d%d",&x,&y);printf("%lld\n",A[x]+B[y]);}}return 0;
}