「杂烩」升降梯上
题面：
题目描述
开启了升降梯的动力之后，探险队员们进入了升降梯运行的那条竖直的隧道，映入眼帘的是一条直通塔顶的轨道、一辆停在轨道底部的电梯、和电梯内一杆控制电梯升降的巨大手柄。
(Nescafe)之塔一共有N层，升降梯在每层都有一个停靠点。手柄有M个控制槽，第i个控制槽旁边标着一个数(Ci)，满足(C1<C2<C3<……<CM)。如果(Ci>0)，表示手柄扳动到该槽时，电梯将上升Ci层；如果(Ci<0)，表示手柄扳动到该槽时，电梯将下降(-Ci)层；并且一定存在一个(Ci=0)，手柄最初就位于此槽中。注意升降梯只能在(1~N)层间移动，因此扳动到使升降梯移动到(1)层以下、(N)层以上的控制槽是不允许的。
电梯每移动一层，需要花费2秒钟时间，而手柄从一个控制槽扳到相邻的槽，需要花费1秒钟时间。探险队员现在在1层，并且想尽快到达N层，他们想知道从1层到N层至少需要多长时间？
输入格式
第一行两个正整数(N、M)。
第二行M个整数(C1、C2……CM)。
输出格式
输出一个整数表示答案，即至少需要多长时间。若不可能到达输出-1。
样例
样例输入
6 3
-1 0 2
样例输出
19
数据范围与提示
手柄从第二个槽扳到第三个槽（(0)扳到(2)），用时(1)秒，电梯上升到3层，用时(4)秒。
手柄在第三个槽不动，电梯再上升到(5)层，用时(4)秒。
手柄扳动到第一个槽（(2)扳到(-1)），用时(2)秒，电梯下降到(4)层，用时(2)秒。
手柄扳动到第三个槽（(-1)扳倒(2)），用时(2)秒，电梯上升到(6)层，用时(4)秒。
总用时为((1+4)+4+(2+2)+(2+4)=19)秒。
对于30% 的数据，满足$ 1≤N≤10，2<=M<=5$。
对于 100% 的数据，满足(1≤N≤1000，2<=M<=20，-N<C1<C2<……<CM<N)。
解法1：暴搜
开题一看：1≤N≤1000，2<=M<=20，貌似搜索也挂不了多少，直接肛
代码：
/*#!/bin/sh
dir=$GEDIT_CURRENT_DOCUMENT_DIR
name=$GEDIT_CURRENT_DOCUMENT_NAME
pre=${name%.*}
g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11
if test $? -eq 0; then
gnome-terminal -x bash -c "time $dir/$pre;echo;read;"
fi*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=2e3+5,INF=0x3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,m,c[maxn],ans=INF,vis[maxn][maxn],f[maxn];
void DFS(int now1,int now2,int sum){//now1是当前层，now2是当前手柄，sum是达到此状态的时间
if(f[now1]>=sum)return;//！！！！！五连警告，考场败在这了，奇怪的终止搜索方法：用新数组存sum，
f[now1]=sum;//如果发现当前的层原来搜过，那么时间一定比原来要长，否则就是又搜了一遍，需要终止递归
if(now1==n){ans=min(ans,sum);return;}
for(int i=m;i>=1;i--){
if(now1+c[i]<1||now1+c[i]>n||c[i]==0)continue;//不合法状态
DFS(now1+c[i],i,sum+abs(i-now2)+2*abs(c[i]));//新时间
}
}
int main(){
freopen("a.in","r",stdin);
n=read(),m=read();
int now=1;
for(int i=1;i<=m;i++){
c[i]=read();
if(c[i]==0)now=i;
}
memset(f,0x3f,sizeof(f));
DFS(1,now,0);
if(ans==INF)cout<<-1;
else cout<<ans;
return 0;
}
解法2：动归
一看又上又下又有状态当然要想到动归，这题状态转移方程很好想：
(f[i][j]=min(f[i][j],f[i-c[j]][k]+abs(j-k)+2*abs(a[j])))
其中i表示当前层，j表示当前手柄，k表示上一手柄（貌似跟暴搜很像）
预处理：(f[1][now]=0) （我在初始位置当然是零时刻）
细节问题（来自某考试过程中五分钟推出关系式见样例不过转身走向搜索的）：我们不管怎么去转移最后一定是有剩余的状态还未参与最后转移的，因为当前状态既可能从上面几层转移过来，也可能从下面几层转移过来的，所以不管正着倒着枚举都不是最优秀的办法。
低端的解决办法：多跑几遍
高端的解决办法：对每一次大循环的f数组判断一下，如果不再变化了说明都达到了最终转移状态
低端版代码
/*#!/bin/sh
dir=$GEDIT_CURRENT_DOCUMENT_DIR
name=$GEDIT_CURRENT_DOCUMENT_NAME
pre=${name%.*}
g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11
if test $? -eq 0; then
gnome-terminal -x bash -c "time $dir/$pre;echo;read;"
fi*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e3+5,INF=0x3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,m,c[maxn],f[maxn][50],ans=INF,g[maxn][50];
int main(){
// freopen("a.in","r",stdin);
n=read(),m=read();
int now=1;
for(int i=1;i<=m;i++){
c[i]=read();
if(c[i]==0)now=i;
}
memset(f,0x3f,sizeof(f));
f[1][now]=0;
for(int p=1;p<=m;p++){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i-c[j]>n||i-c[j]<1)continue;
for(int k=1;k<=m;k++)
f[i][j]=min(f[i][j],f[i-c[j]][k]+abs(j-k)+2*abs(c[j]));
}
}
}
for(int i=1;i<=m;i++)ans=min(ans,f[n][i]);
if(ans==INF)cout<<-1;
else cout<<ans;
return 0;
}
高端版
/*#!/bin/sh
dir=$GEDIT_CURRENT_DOCUMENT_DIR
name=$GEDIT_CURRENT_DOCUMENT_NAME
pre=${name%.*}
g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11
if test $? -eq 0; then
gnome-terminal -x bash -c "time $dir/$pre;echo;read;"
fi*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e3+5,INF=0x3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,m,c[maxn],f[maxn][50],ans=INF,g[maxn][50];
bool panduan(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]!=f[i][j])return 1;
}
}
return 0;
}
void turnback(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
g[i][j]=f[i][j];
}
}
}
int main(){
// freopen("a.in","r",stdin);
n=read(),m=read();
int now=1;
for(int i=1;i<=m;i++){
c[i]=read();
if(c[i]==0)now=i;
}
memset(f,0x3f,sizeof(f));
f[1][now]=0;
for(int i=1;i<=m;i++){if(now!=i)f[1][i]=abs(i-now);}
while(panduan()){
turnback();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j==now)continue;
if(i-c[j]>n||i-c[j]<1)continue;
for(int k=1;k<=m;k++){
if(k==now)continue;
f[i][j]=min(f[i][j],f[i-c[j]][k]+abs(j-k)+2*abs(c[j]));
//cout<<i<<"=i j="<<j<<" k= "<<k<<" i-k="<<i-c[k]<<" f[i][j] ="<<f[i][j]<<endl;
}
if(i==n)ans=min(ans,f[n][j]);
}
}
}
if(ans==INF)cout<<-1;
else cout<<ans;
return 0;
}
解法3：最短路
万万想不到能用DP还要用最短路（某道馅饼题跑了拓扑，直接从100pts->40pts）
1.二维压一维
2.奇妙的建图
代码
/*#!/bin/sh
dir=$GEDIT_CURRENT_DOCUMENT_DIR
name=$GEDIT_CURRENT_DOCUMENT_NAME
pre=${name%.*}
g++ -O2 $dir/$name -o $pre -g -Wall -std=c++11
if test $? -eq 0; then
gnome-terminal -x bash -c "time $dir/$pre;echo;read;"
fi*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=4e7+5,INF=0x3f3f3f3f;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return s*w;
}
int n,m,c[maxn],ans=INF,head[maxn],tot,dis[maxn],vis[maxn];
int turnit(int x,int y){
return (x-1)*m+y;
}
struct Edge{
int next,to,dis;
}e[maxn];
void Add(int x,int y,int z){
e[++tot].to=y;
e[tot].next=head[x];
e[tot].dis=z;
head[x]=tot;
}
queue<int> q;
void spfa(int S){
for(int i=1;i<=n*m;i++)vis[i]=0,dis[i]=INF;
dis[S]=0;vis[S]=1;q.push(S);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
for(int x=head[u];x;x=e[x].next){
int v=e[x].to;
if(dis[v]>dis[u]+e[x].dis){
dis[v]=dis[u]+e[x].dis;
if(!vis[v])vis[v]=1,q.push(v);
}
}
}
}
int main(){
n=read(),m=read();
int now=1;
for(int i=1;i<=m;i++){
c[i]=read();
if(c[i]==0)now=i;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=m;k++)
Add(turnit(i,j),turnit(i+c[k],k),abs(j-k)+2*abs(c[k]));
spfa(turnit(1,now));
for(int i=1;i<=m;i++){
ans=min(dis[turnit(n,i)],ans);
//cout<<dis[turnit(n,i)]<<endl;
}
if(ans==INF)cout<<-1;
else cout<<ans;
return 0;
}