P7936 [COCI 2007/2008 #5] BARICA
题目描述
Barica 是一只非同寻常的青蛙。她住在一个池塘里，有NNN片漂浮在水面上的荷叶。这些荷叶的编号为111到NNN，位置可以用一对坐标表示。Barica 可以在这些荷叶上跳来跳去，但是她害怕斜着跳和朝负方向跳。
准确的说，她可以从坐标(x1,y1)(x_1,y_1)(x1,y1)跳到另一个坐标(x2,y2)(x_2,y_2)(x2,y2)仅当：
x2>x1x_2>x_1x2>x1且y2=y1y_2=y_1y2=y1或者
y2>y1y_2>y_1y2>y1且x2=x1x_2=x_1x2=x1。
对于每一片荷叶，我们知道其附近的苍蝇数量。Barika 可以吃掉所有在她荷叶附近的苍蝇。
Barica 每吃一只苍蝇会获得111个单位的能量，每进行一次跳跃消耗KKK个单位的能量。如果 Barica 没有足够的能量，她就不能进行跳跃。
Barica 想通过111号植物到达NNN号植物，并获得尽可能多的能量。Barica 开始时没有能量，必须通过吃掉111号植物附近的苍蝇来获取能量。
找到使得 Barica 达到目标的一种可行路径。
输入格式
第一行，两个整数NNN和KKK。
接下来NNN行，每行包含三个整数xix_ixi，yiy_iyi和ziz_izi，表示第iii号荷叶的坐标为(xi,yi)(x_i,y_i)(xi,yi)，且其附近有ziz_izi只苍蝇。
输出格式
第一行，输出到达终点后能量单位数量。
第二行，输出一个整数LLL，表示 Barica 需要经过的植物个数。必须包含111号和NNN号植物。
接下来LLL行，依次输出 Barica 需要经过的植物坐标。
输入输出样例 #1
输入 #1
6 5 1 1 5 2 1 5 1 2 4 2 3 5 3 2 30 3 3 5输出 #1
5 4 1 1 2 1 2 3 3 3输入输出样例 #2
输入 #2
8 10 1 1 15 2 2 30 1 2 8 2 1 7 3 2 8 2 3 7 4 2 100 3 3 15输出 #2
36 5 1 1 1 2 2 2 3 2 3 3输入输出样例 #3
输入 #3
9 5 5 5 10 6 5 2 7 5 1 5 6 2 6 6 6 7 6 2 5 7 1 6 7 2 7 7 1输出 #3
2 3 5 5 7 5 7 7说明/提示
对于100%100\%100%的数据，2≤N≤3×1052\le N\le 3\times 10^52≤N≤3×105，1≤K≤10001\le K\le 10001≤K≤1000，0≤xi,yi≤1050\le x_i,y_i\le 10^50≤xi,yi≤105，0≤zi≤10000\le z_i\le 10000≤zi≤1000。
输入数据保证有解，但不保证有唯一解。
本题分值按照原比赛设置，满分707070分。
C++实现
#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=3e5+10,M=1e5+10;structnode{intx,y,z,idx;}a[N];intn,k,st=1,ed=1,dp[N],fx[M],fy[M],from[N];boolcmp(node a,node b){if(a.x==b.x)returna.y<b.y;elsereturna.x<b.x;}voidprint(intid,intnum){if(!from[id]){printf("%d\n%d %d\n",num,a[id].x,a[id].y);return;}print(from[id],num+1);printf("%d %d\n",a[id].x,a[id].y);//应该都能看懂吧}intmain(){scanf("%d %d",&n,&k);for(inti=1;i<=n;i++){scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].z);a[i].idx=i;//记录编号}sort(a+1,a+1+n,cmp);//排序，先后顺序while(a[st].idx!=1)st++;//找到第一个点while(a[ed].idx!=n)ed++;//找到最后一个点dp[st]=a[st].z,fx[a[st].x]=st,fy[a[st].y]=st;//记录最初状态for(inti=st+1;i<=ed;i++){//这里舍弃掉了一些无法转移的点，这些点不可能从第一个点转移或转移到最后一个点intxx=a[i].x,yy=a[i].y,w=a[i].z,prex=fx[xx],prey=fy[yy];//提取点的信息if(prex&&dp[prex]>=k&&dp[prex]+w-k>dp[i])dp[i]=dp[prex]+w-k,from[i]=prex;//从同行的点转移if(prey&&dp[prey]>=k&&dp[prey]+w-k>dp[i])dp[i]=dp[prey]+w-k,from[i]=prey;//从同列的点转移if(dp[i]>dp[fx[xx]])fx[xx]=i;if(dp[i]>dp[fy[yy]])fy[yy]=i;//更新fx,fy}printf("%d\n",dp[ed]);//输出最大能量值print(ed,1);//输出最大路径return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
