正题

题面链接:https://www.luogu.com.cn/problem/U142298?contestId=37766

---

题目大意

$n$个人有起点和终点，按顺序上车，但下车可以任意顺序，车最多同时只能载$4$个人。求车的最短路程。

---

解题思路

显然我们需要把上次上车的人，现在在车上的人下车位置，车的位置压入状态中。第二个比较麻烦，也比较大，我们可以预处理把一些没用的状态去掉，压缩一下，然后$dp$即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define lowbit(x) (x&-x) #define gmin(x,y) x=min(x,y) using namespace std; const int N=1024; int n,k,cnt,f[2100][N][10]; int p[11][11][11][11],rfn[N][4],q[4]; int main() {scanf("%d%d",&n,&k);for(int x1=0;x1<=k;x1++)for(int x2=x1;x2<=k;x2++)for(int x3=x2;x3<=k;x3++)for(int x4=x3;x4<=k;x4++){p[x1][x2][x3][x4]=cnt;rfn[cnt][0]=x1;rfn[cnt][1]=x2;rfn[cnt][2]=x3;rfn[cnt][3]=x4;cnt++;}for(int x1=0;x1<=k;x1++)for(int x2=0;x2<=k;x2++)for(int x3=0;x3<=k;x3++)for(int x4=0;x4<=k;x4++){q[0]=x1;q[1]=x2;q[2]=x3;q[3]=x4;sort(q,q+4);p[x1][x2][x3][x4]=p[q[0]][q[1]][q[2]][q[3]];}memset(f,0x3f,sizeof(f));f[0][p[k][k][k][k]][0]=0;int tmp=0;for(int i=1;i<=n;i++){int x,y;tmp^=1;memset(f[tmp],0x3f,sizeof(f[tmp]));scanf("%d%d",&x,&y);x--;y--; // x=1;y=10;for(int j=0;j<cnt;j++){if(rfn[j][3]!=k)continue;q[0]=rfn[j][0];q[1]=rfn[j][1];q[2]=rfn[j][2];q[3]=y;int z=p[q[0]][q[1]][q[2]][q[3]];for(int w=0;w<k;w++)gmin(f[tmp][z][x],f[!tmp][j][w]+abs(w-x)+1);}for(int j=0;j<cnt;j++){q[0]=rfn[j][0];q[1]=rfn[j][1];q[2]=rfn[j][2];q[3]=rfn[j][3];for(int w=0;w<k;w++){if(q[0]!=k)gmin(f[tmp][p[k][q[1]][q[2]][q[3]]][q[0]],f[tmp][j][w]+abs(w-q[0])+1);if(q[1]!=k)gmin(f[tmp][p[q[0]][k][q[2]][q[3]]][q[1]],f[tmp][j][w]+abs(w-q[1])+1);if(q[2]!=k)gmin(f[tmp][p[q[0]][q[1]][k][q[3]]][q[2]],f[tmp][j][w]+abs(w-q[2])+1);if(q[3]!=k)gmin(f[tmp][p[q[0]][q[1]][q[2]][k]][q[3]],f[tmp][j][w]+abs(w-q[3])+1);}}}int ans=2147483647;for(int i=0;i<k;i++)ans=min(ans,f[tmp][p[k][k][k][k]][i]);printf("%d",ans);return 0; }

总结

以上是生活随笔为你收集整理的[2020.11.25NOIP模拟赛]出租车【dp】的全部内容，希望文章能够帮你解决所遇到的问题。

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