关键词：
题目描述
一张 n 个点 m 条有向边的图上，有 q 个配送需求，需求的描述形式为 (si,ti,li,ri)( s_i , t_i , l_i , r_i )(si?,ti?,li?,ri?)，即需要从点 si 送到 ti， 在时刻 li 之后（包括 lil_ili? ）可以在 sis_isi? 领取货物，需要在时刻 ri 之前（包括 ri）送达 ti ，每个任务只需完成一次。
图上的每一条边均有边权，权值代表通过这条边消耗的时间。在时刻 000 有一个工作人员在点 1 上，求他最多能完成多少个配送任务。
在整个过程中，可以认为领货跟交货都是不消耗时间的，时间只花费在路程上。当然在一个点逗留也是允许的。
输出格式
一个整数，表示最多能完成的任务数量。
样例输入
5 4 3 1 2 1 2 3 1 3 4 1 4 5 1 1 2 3 4 2 3 1 2 3 4 3 4
样例输出
2
样例解释
工作人员可以在时刻 1 到达点 2 ，领取第二个货物后在时刻 2 到达点 3 后交货，逗留到时刻 4 ，领取第三个货物，在时刻 4 到达点 4 并交货。
• 首先的首先，需要明确配送的方式。在配送的途中手中不一定只有一份外卖！
然后出于对数据的敏感，易想到用进制数表示状态。
• 由于每一份外卖有按照程序有三种状态，所以用三进制表示外卖的整体状态，
在dp数组中作为一个维度，剩下时间和当前位置。
• 由于时间是数据中最大的存在，成为了dp的对象，当前位置成为了另一个状
态维度。
• 转移的话，只是合法性的判断了。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,q,x,y,z; 4 int dis[25][25]; 5 int f[60050][25],w,now,ans; 6 int base[15],s[15],t[15],l[15],r[15]; 7 int main() 8 9 base[0]=1; 10 for(int i=1;i<=11;++i) 11 base[i]=base[i-1]*3; 12 memset(dis,0x3f,sizeof(dis)); 13 memset(f,0x3f,sizeof(f));f[0][1]=0; 14 scanf("%d%d%d",&n,&m,&q); 15 for(int i=1;i<=m;++i) 16 17 scanf("%d%d%d",&x,&y,&z); 18 dis[x][y]=min(dis[x][y],z); 19 20 for(int i=1;i<=n;++i) 21 dis[i][i]=0; 22 for(int k=1;k<=n;++k) 23 for(int i=1;i<=n;++i) 24 for(int j=1;j<=n;++j) 25 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 26 for(int i=0;i<q;++i) 27 scanf("%d%d%d%d",&s[i],&t[i],&l[i],&r[i]); 28 m=base[q]-1; 29 for(int i=0;i<=m;++i) 30 31 for(int j=1;j<=n;++j) 32 33 for(int k=0;k<q;++k) 34 35 now=i/base[k]%3; 36 if(now==0) 37 f[i+base[k]][s[k]]=min(f[i+base[k]][s[k]],max(f[i][j]+dis[j][s[k]],l[k])); 38 else if(now==1&&f[i][j]+dis[j][t[k]]<=r[k]) 39 f[i+base[k]][t[k]]=min(f[i+base[k]][t[k]],f[i][j]+dis[j][t[k]]); 40 41 42 if(f[i][j]<f[0][0]) 43 44 w=0; 45 for(int k=0;k<=10;++k) 46 if(i/base[k]%3==2) 47 ++w; 48 ans=max(ans,w); 49 50 51 52 printf("%d",ans); 53 return 0; 54
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,q,x,y,z; 4 int dis[25][25]; 5 int f[60050][25],w,now,ans; 6 int base[15],s[15],t[15],l[15],r[15]; 7 int main() 8 9 base[0]=1; 10 for(int i=1;i<=11;++i) 11 base[i]=base[i-1]*3; 12 memset(dis,0x3f,sizeof(dis)); 13 memset(f,0x3f,sizeof(f));f[0][1]=0; 14 scanf("%d%d%d",&n,&m,&q); 15 for(int i=1;i<=m;++i) 16 17 scanf("%d%d%d",&x,&y,&z); 18 dis[x][y]=min(dis[x][y],z); 19 20 for(int i=1;i<=n;++i) 21 dis[i][i]=0; 22 for(int k=1;k<=n;++k) 23 for(int i=1;i<=n;++i) 24 for(int j=1;j<=n;++j) 25 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 26 for(int i=0;i<q;++i) 27 scanf("%d%d%d%d",&s[i],&t[i],&l[i],&r[i]); 28 m=base[q]-1; 29 for(int i=0;i<=m;++i) 30 31 for(int j=1;j<=n;++j) 32 33 if(f[i][j]==f[0][0]) 34 continue; 35 for(int k=0;k<q;++k) 36 37 now=i/base[k]%3; 38 if(now==0) 39 f[i+base[k]][s[k]]=min(f[i+base[k]][s[k]],max(f[i][j]+dis[j][s[k]],l[k])); 40 else if(now==1&&f[i][j]+dis[j][t[k]]<=r[k]) 41 f[i+base[k]][t[k]]=min(f[i+base[k]][t[k]],f[i][j]+dis[j][t[k]]); 42 43 44 w=0; 45 for(int k=0;k<=10;++k) 46 if(i/base[k]%3==2) 47 ++w; 48 ans=max(ans,w); 49 50 51 printf("%d",ans); 52 return 0; 53
这两份代码在思路上是完全一致的。但是……
相似的结果还发生在另一个状压题上（第二份代码直接是TLE 了）：
这究竟是种怎样的操作？
如果当前状态完全不可能被转移到的话，就完全没必要对它进行暴力扩展了，果断continue。
#6177.「美团codem初赛roundb」送外卖2（floyed+三进制枚举）(代码片段)
题目大意：一张 个点 条有向边的图上，有 个配送需求，需求的描述形式为 ，即需要从点 送到 ，在时刻 之后（包括 ）可以在 领取货物，需要在时刻 &nb... 查看详情
「美团codem初赛roundb」景区路线规划概率dp
题意游乐园被描述成一张 n个点，m条边的无向图（无重边，无自环）。每个点代表一个娱乐项目，第 i个娱乐项目需要耗费 ci分钟的时间，会让小y和妹子的开心度分别增加 h1i,h2i，他们俩初始的开心度都是 0。... 查看详情
codem美团点评编程大赛初赛a轮
...锻炼下就行了。身体训练时间限制：1秒空间限制：32768K美团外卖的配送员用变速跑的方式进行身体训练。他们训练的方式是：n个人排成一列跑步，前后两人之间相隔u米，每个人正常速度均为v米/秒。当某个配送员排在最后的时... 查看详情
loj#6164.「美团codem初赛rounda」数列互质
link: https://loj.ac/problem/6164 莫队傻题，直接容斥做。 #include<bits/stdc++.h>#definemaxn100005#definepbpush_backusingnamespacestd;vector<int>g[maxn];structask intl,r,K,num,bl; bool 查看详情
codem初赛t4分解质因数+暴力
题目描述树链是指树里的一条路径。美团外卖的形象代言人袋鼠先生最近在研究一个特殊的最长树链问题。现在树中的每个点都有一个正整数值，他想在树中找出最长的树链，使得这条树链上所有对应点的值的最大公约数大于1... 查看详情
美团2017年codem大赛-初赛b轮黑白树(树形dp)
大意:给定树,初始每个点全为白色,点$i$有权值$k_i$,表示选择$i$后,所有距离$i$小于$k_i$的祖先(包括i)会变为黑色,求最少选多少个点能使所有点变为黑色. 链上情况的话,直接从链头开始做一次线性dp就行了,但是显然不能拓展... 查看详情
codem美团点评编程大赛初赛b轮黑白树dfs深搜+暴力
[编程题]黑白树时间限制：1秒空间限制：32768K一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最... 查看详情
饿了么，美团，百度外卖哪个工资待遇好
饿了么，美团，百度外卖哪个工资待遇好美团外卖的工资待遇较好，具体的工资需要根据外卖员的送单量而定。美团外卖一天能送几单，主要取决于对送餐路线的熟练程度和送餐技巧，通常新手外卖员一天挣到两百左右。美团外... 查看详情
codem美团点评编程竞赛资格赛题
最近看到牛课网美团一个编程竞赛，想着做做看，结果一写就是两天。。真是写不动了啊。话不多说，下面开始我的题解。题目大致还是比较考察思维和代码能力（因为自己代码能力较弱，才会觉得比较考察代码能力吧==！），... 查看详情
codem初赛b轮
做什么啊，我这么菜，应该弃赛的[编程|1500分]子串时间限制：3秒空间限制：32768K题目描述给出一个正整数n，我们把1..n在k进制下的表示连起来记为s(n,k)，例如s(16,16)=123456789ABCDEF10,s(5,2)=11011100101。现在对于给定的n和字符串t，我... 查看详情
美团面试都面不过？我又不是去送外卖的！美团java面试经历总结一面二面三面
美团面试都面不过？我又不是去送外卖的！美团Java面试经历总结【一面、二面、三面】这篇文章主要介绍了美团Java面试经历,总结分析了美团java三轮面试中所遇到的各种问题,对于参与java面试有一定参考价值,需要的朋友... 查看详情
美团codem资格赛第二题
锦标赛时间限制：1秒空间限制：32768K组委会正在为美团点评CodeM大赛的决赛设计新赛制。比赛有n个人参加（其中n为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设... 查看详情
美团众包是啥意思?
参考技术A问题一：美团众包是什么？是一个***帮助美团送外卖的，在里边你可以接单帮助送外卖赚钱。问题二：美团众包中的众包是什么意思？其实就是讲配送平台开放话，让所有用户都可以成为配送员，只要注册美团众包，... 查看详情
2017codem初赛b场
A、合并字符串价值（loj6174）分析：普通暴力：枚举两个分界线，那么ans=Σmin(Al(c)+Bl(c),Ar(c)+Br(c))，这样是O(n^2)，会TLE考虑枚举a的分界线，b的答案根据之前的答案进行转移显然，4个字母AGCT可以单独考虑假设当前a分界线下，a... 查看详情
美团外卖系统架构演进与稳定性的探索
简单介绍一下外卖现在的情况：我们从2013年10月份做外卖的事情，是从餐饮外卖开始的。经过两年多的发展，我们不光可以提供餐饮外卖，也可以提供水果、鲜花、蛋糕、下午茶甚至是超市和便利店一些外送的服务。我们做外卖... 查看详情
codem资格赛1
题目描述美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。具体地说，就是在第二段音频中找到一个长... 查看详情
libreojl6210「美团codem决赛」tree(代码片段)
难度：$\\texttt?$链接难度：\\(\\texttt?\\)有一颗\\(n\\)个点的树，每个点有权值\\(x_i\\)，定义一条简单路径的权值为\\(f(a_1\\toa_2\\to...\\toa_k)=\\fracx_a_1\\timesx_a_2\\times...\\timesx_a_kk\\)，求最小的\\(f(a_1\\toa_2\\to...\\toa_k)\\)值。数据范 查看详情
codem-4
...ct-question">n个小区排成一列，编号为从0到n-1。一开始，美团外卖员在第0号小区，目标为位于第n-1个小区的配送站。<br>给定两个整数数列a[0]~a[n-1]和b[0]~b[n-1]，在每个小区i里你有两种选择：<br& 查看详情