题目大意

给一个n*n的矩形，里面有若干个数，给出t个询问，求点(x,y)的左上角和右下角的数加起来有多少
不知为何开1001的数组会爆

思路

看样例很容易想到用dp，哪张草稿纸随便搞搞即可得:
设f[i,j]为包括当前点的左上角的和
f[i][j]=a[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1]
同理得右下角的dp方程
所以对于每一个询问(x,y)答案为f[x-1][y-1]+f2[x+1][y+1]

#include 
#define maxn 1005
int f[maxn][maxn],a[maxn][maxn],f2[maxn][maxn];
int main()
{
    freopen("scout.in","r",stdin); 
    freopen("scout.out","w",stdout);
    int n,t;
    scanf("%d%d",&n,&t);
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1]+a[i][j];
        }
    }
    for (int i=n;i>=1;i--)
    {
        for (int j=n;j>=1;j--)
        {
            f2[i][j]=f2[i][j+1]+f2[i+1][j]-f2[i+1][j+1]+a[i][j];
        }
    }
    for (int i=1;i<=t;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",f[x-1][y-1]+f2[x+1][y+1]);
    }
}