博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[JOI2017] サッカー (Soccer)
阅读量:5718 次
发布时间:2019-06-18

本文共 3227 字,大约阅读时间需要 10 分钟。

原题题面看不懂的可以看下面的\(CJ\)版中文题面

1196604-20171031221308060-590652878.png
1196604-20171031221312451-1544387627.png
1196604-20171031221315763-1270703325.png
1196604-20171031221321654-1461653105.png
1196604-20171031221325420-2028202851.png
1196604-20171031221329873-455736657.png
1196604-20171031221333857-2047265374.png
1196604-20171031221337341-930372026.png
1196604-20171031221341591-1791722364.png
1196604-20171031221345060-1163633269.png
1196604-20171031221348576-1026783643.png
1196604-20171031221353654-1309568745.png
$
$
\(CJ\)版:
1196604-20171031222043107-2047948331.png
1196604-20171031222049263-1567728068.png
1196604-20171031222055404-2142898151.png
1196604-20171031222059513-387951104.png
1196604-20171031222103826-478366037.png
1196604-20171031222109388-1353418503.png
$
$
这道题是\(JOI\)\(T4\),放到联赛大概就是\(Day2,T3\)的难度
$
$
\(5\)分:
这一档分就是一个分类讨论,因为\(N=2\)
一共有\(3\)种情况可以出现最优解:

  1. \(1\)带球跑到\(2\)\(ans=C*(\left|h1-h2\right|+\left|w1-w2\right|)\)
  2. \(1\)带球纵向跑到与\(2\)齐平,踢球,\(ans=C*\left|h1-h2\right|+A*\left|w1-w2\right|+B\)
  3. \(1\)带球横向跑到与\(2\)齐平,踢球,\(ans=C*\left|w1-w2\right|+A*\left|h1-h2\right|+B\)

另外\(30\)分:

\(A=0\),也就是说踢球不取决于距离,踢球的花费完全取决于踢球的次数。
所以这里有两个结论,为了达到最优解,一个人不会踢球两次,一个人不会跑到其他地方去捡球来踢,这个结论画几个图就能够看出来,就不证明了。
那么整个过程就可以简化成:一个人带球跑,踢球,另一人接球,带球,再踢球。。。
这样就可以通过这个求出一个点到另一个点的最小花费,最后跑个最短路就可以求出来

\(100\)分:

这一问没有了\(A=0\)的条件,不过没有关系,上面的结论依然能用,一个人不会踢球两次。
而且这一问的\(N\)比较大,所以不可能直接对运动员进行处理。
然后我们就来想一下其他的做法。满数据的\(H\)\(W\)都比较小,我们可以把对运动员的处理换成直接对网格的处理。
\(a[x][y]\)为步行到\((x,y)\)这个点的最小花费,这个可以\(bfs\)处理出来。
\(ans[x][y][k]\),为在\((x,y)\)这个点时的几个状态的最小疲劳值,当\(0\le k\le3\)时,表示球从\(k\)方向滚到\((x,y)\)的最小疲劳值;当\(k=4\)时,表示运动员在\((x,y)\)持球的最小疲劳值。
那么具体怎么转移呢?
对于一个\(k=4\)的状态,它可以这样转移:

  1. 向各个方向走一格,\(ans[x'][y'][4]=ans[x][y][4]+C\)
  2. 向各个方向踢出球,\(ans[x][y][k']=ans[x][y][4]+B\)

对于一个\(k!=4\)的状态,它可以这样转移:

  1. 继续向前滚,\(ans[x'][y'][k]=ans[x][y][k]+A\)
  2. 一个运动员跑过来持球,\(ans[x][y][4]=ans[x][y][k]+C*a[x][y]\)

这个算法可以通过\(Dij\)来实现,最终的答案就是\(ans[hn][wn][4]\)

时间复杂度:\(O(HW*logHW)\)

$
$

//made by Hero_of_Someone#include
#include
#include
#define inf (1e17)#define ll long long#define il inline#define RG registerusing namespace std;il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar(); if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }il void File(){freopen("soccer.in","r",stdin); freopen("soccer.out","w",stdout);}int h,w,n;ll A,B,C;ll a[540][540];ll dis[50000010];int H[1000010],W[1000010];int qh[1000010],qw[1000010];bool vis[540][540],v[50000010];int dh[]={0,-1,0,1},dw[]={-1,0,1,0};struct heap{#define fa (x>>1)#define ls (x<<1)#define rs (x<<1|1) int b[50000010],id[50000010],len; il int top(){ return b[1]; } il void push(RG int u){ if(!id[u]) id[u]=++len,b[len]=u; RG int x=id[u]; while(fa){ if(dis[b[x]]>=dis[b[fa]]) break; swap(b[x],b[fa]),id[b[x]]=x,id[b[fa]]=fa,x=fa; } return; } il void pop(){ id[b[1]]=0,b[1]=b[len--]; if (len) id[b[1]]=1; RG int x=1,son; while(ls<=len){ son=(rs<=len && dis[b[rs]]
h||yy<0||yy>w) continue; if(a[xx][yy]!=inf) continue; a[xx][yy]=a[x][y]+1; qh[tl]=xx,qw[tl++]=yy; } hd++; }}il void work(){ for(RG int i=0;i<=h;i++) for(RG int j=0;j<=w;j++) for(RG int k=0;k<=4;k++) dis[i*5000+j+k*10000000]=inf; RG int t=H[0]*5000+W[0]+40000000; dis[t]=0; que.push(t); while(que.len){ RG int q=que.top();que.pop(); if(v[q]) continue; v[q]=1; RG ll c=dis[q]; RG int dir=q/10000000;q%=10000000; RG int x=q/5000,y=q%5000; if(dir==4){ for(RG int i=0;i<4;i++){ RG int xx=x+dh[i],yy=y+dw[i]; if(xx<0||xx>h||yy<0||yy>w) continue; RG int t=xx*5000+yy+40000000; if(c+C
h||yy<0||yy>w) continue; t=xx*5000+yy+10000000*dir; if(c+A

(没事干写手写堆来玩玩)

转载于:https://www.cnblogs.com/Hero-of-someone/p/7764055.html

你可能感兴趣的文章
Spring+Mybatis项目中通过继承AbstractRoutingDataSource实现数据库热切换
查看>>
让Alert弹窗只弹出一次
查看>>
Berkeley DB 源代码分析 (1) --- 代码特征与游标的实现
查看>>
用友软件操作流程(新建年度帐、年度结转步骤)
查看>>
vsftpd 服务器报错:500 OOPS: vsftpd: refusing to run with writable root inside chroot()
查看>>
mysql权限管理
查看>>
我的友情链接
查看>>
Exchange一些不常用到的功能
查看>>
让你快速上手的Glide4.x教程
查看>>
浮动和清除(闭合)浮动
查看>>
微信小程序注册流程
查看>>
LR录制脚本时IE打不开的原因
查看>>
类的基础
查看>>
微博自动化测试
查看>>
Sublime Text 2.0.2,Build 2221注册码
查看>>
js scroll事件
查看>>
day08 文件操作
查看>>
最长递增子序列 动态规划
查看>>
「小程序JAVA实战」微信小程序工程结构了解(五)
查看>>
使用列表
查看>>