[jzoj 5775]【NOIP2008模拟】农夫约的假期 (前缀和+递推)

传送门

Description

在某国有一个叫农夫约的人，他养了很多羊，其中有两头名叫mm和hh，他们的歌声十分好听，被当地人称为“魔音”······
农夫约也有自己的假期呀！他要去海边度假，然而mm和hh不能离开他。没办法，他只好把他们两个带上。
到了海边，农夫约把他的羊放在一个(nn)的矩阵（有nn个方格）里。mm和hh十分好动，他们要走到m(m<=n*n)个地方，第i个地方的坐标为(x[i]（行）,y[i]（列）)，每到一个地方他们会高歌一曲，制造q[i]点魔音值，因为他们的魔音十分独特，他们的声音只能横着或竖着传播。每传播一格，魔音值会增加1。（传播的格子数取最小的）接下来农夫约要住酒店。为了方便照顾小羊们，他选的酒店的坐标要在矩阵内。但小羊们的魔音让他十分头疼。他想求出魔音值最小的地方。
他还要享受他的假期，所以他把这个任务交给你了，加油（^_^）。

Input

第一行输入n、m和z。
接下来m行，每行3个正整数x[i],y[i]和q[i]。

Output

第一行一个整数表示魔音值最小是多少。
接下来一行两个正整数zb1和zb2，表示魔音值最小的地方的坐标（如果有多个答案，输出横坐标最小的情况下，纵坐标最小的）。

Sample Input

3 3 1
1 1 1
1 2 1
1 3 1

Sample Output

5
1 2

样例解释：（1，1）的初始魔音值为1，（1，2）的初始魔音值为1，（1，3）的初始魔音值为1，（1，1）与（1，2）的距离为1（abs(1-1)+abs(1-2)），传播过程中的魔音值为1*z=1。（1，2）与（1，2）的距离为0,传播过程中的魔音值为0，（1，3）与（1，2）的距离为1，传播过程中的魔音值为1。总魔音值为1+1+1+1+0+1=5。

Data Constraint

10%的数据，n<=10（来自题目的馈赠）.
30%的数据，n<=1000.
100%的数据，0<n<=100000，0<m<=100000,0<z<=10，0<q[i]<=100.

Hint

题目保证z=1

Solution

可以暴力求出第一个点的，然后将它向后转移

Code

//By Menteur_Hxy #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define int long long #define F(i,a,b) for(i=(a);i<=(b);i++) #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin)),p1==p2?EOF:*p1++) using namespace std;char buf[1<<20],*p1,*p2; inline int read() {int x=0,f=1; char c=getchar();while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();return x*f; }const int N=100010; int xid[N],yid[N],da[N],xls[N],yls[N];signed main() {freopen("shuru.in","r",stdin);freopen("shuru.out","w",stdout);int n,m,z,i,ans=0,xsum=0,ysum=0,xmi=1000000000000ll,ymi=1000000000000ll,xans,yans;n=read(),m=read(),z=read();F(i,1,m) xid[read()]++,yid[read()]++,ans+=read();F(i,1,n) xls[i]=xls[i-1]+xid[i],yls[i]=yls[i-1]+yid[i]; // F(i,1,n) printf("%d ",xls[i]);puts(""); // F(i,1,n) printf("%d ",yls[i]);puts("");F(i,1,n-1) xsum+=m-xls[i],ysum+=m-yls[i];F(i,1,n) { // printf("%lld %lld\n",xsum,ysum);if(xsum<xmi) xmi=xsum,xans=i;if(ysum<ymi) ymi=ysum,yans=i;xsum+=(xls[i]<<1)-m;ysum+=(yls[i]<<1)-m;}printf("%lld\n%lld %lld",ans+xmi+ymi,xans,yans);return 0; }

转载于:https://www.cnblogs.com/Menteur-Hxy/p/9451615.html

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的[jzoj 5775]【NOIP2008模拟】农夫约的假期 (前缀和+递推)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。