天上的星星-DP

DP+分割

题目-天上的星星

在一个星光璀璨的夜晚，蒜头巨一颗一颗的数天上的星星。
蒜头君给天上巧妙的画了一个直角坐标系，让所有的星星都分布在第一象限。天上有$n$颗星星，他能知道每一颗星星的坐标和亮度。
现在，蒜头君问自己$q$次，每次他问自己每个矩形区域的星星的亮度和是多少(包含边界的星星)

输入格式

第一行输入一个整数$n(1\le n\le 50000)$表示星星的数量。
接下来$n$行，每行输入三个整数$x,y,w(0\le x,y,z\le 2000)$, 表示在坐标$(x,y)$有一颗亮度为$w$的星星。注意一个点可能有多个星星。
接下来一行输入一个整数$q(1\le q\le 50000)$，表示查询的次数。
接下来$q$行，每行输入四个整数$x_1,y_1,x_2,y_2$，期中$(x1,y1)表示查询的矩形的左下角的坐标，$(x_2, y_2)$表示查询的矩形的右上角的坐标，$0\le x_1\le x_2\le 2000,0\le y_1\le y_2\le 2000$

输出格式

对于每一次查询，输出一行一个整数，表示查询的矩形区域内的星星的亮度综合。

解析

看到这道题，由于坐标的范围只有2000，第一反应考虑预处理计算出从点$(0,0)$到点$(x,y)$区域内星星的总亮度。这个考虑用DP加矩形分割来计算, 可以这样思考，$dp[x][y]$表示从点$(0,0)$到点$(x,y)$的亮度之和，那么可以得到:$dp[x][y]=dp[x][y]+dp[x-1][y]+dp[x][y-1]-dp[x-1][y-1]$, 对0进行特判即可，查询的时候为$ans=dp[x_2][y_2]-dp[x_2][y_1-1]-dp[x_1-1][y_2]+dp[x_1-1][y_1-1]$, 依然需要对0的地方特别处理一下即可。

AC代码

//  小学生一发的刷题之路
//
//  dp+矩形分割
//
//#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>                //双向队列;
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <vector>
#include <cstdlib>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const double PI=acos(-1.0);
const double eps=1e-8;
const int maxn=2000+5;
const int maxm=1e6+5;
const ll mod=1e9+7;
const int INF=1e8;
template<class T>
inline void read(T &ret){       //快速输入模版;ret=0;int f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}ret*=f;
}
template <class T>
inline void out(T ret){     //快速输出模版;if(ret>9){out(ret/10);}putchar(ret%10+'0');
}
int n,q,dp[maxn][maxn];int main()
{memset(dp,0,sizeof(dp));scanf("%d",&n);int x,y,w;for(int i=1;i<=n;i++){scanf("%d %d %d",&x,&y,&w);dp[x][y]+=w;}for(int i=0;i<=2000;i++)for(int j=0;j<=2000;j++){if(i==0&&j==0){continue;}else if(i==0){dp[i][j]=dp[i][j]+dp[i][j-1];}else if(j==0){dp[i][j]=dp[i][j]+dp[i-1][j];}else{dp[i][j]=dp[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];}}//cout<<dp[2000][2000]<<endl;scanf("%d",&q);int x1,y1,x2,y2,ans;while(q--){scanf("%d %d %d %d",&x1,&y1,&x2,&y2);if(x1==0&&y1==0){printf("%d\n",dp[x2][y2]);}else if(x1==0){ans=dp[x2][y2]-dp[x2][y1-1];printf("%d\n",ans);}else if(y1==0){ans=dp[x2][y2]-dp[x1-1][y2];printf("%d\n",ans);}else{ans=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];printf("%d\n",ans);}}return 0;
}

新的开始，每天都要快乐哈。