CH 5102 Mobile Service(线性DP)
2024-08-30 08:15:41
CH 5102 Mobile Service
$ solution: $
这道题很容易想到DP,因为题目里已经说了要按顺序完成这些请求。所以我们可以线性DP,但是这一题的状态不是很好设,因为数据范围有点大,而且我们需要记录三个人的位置信息。但是我们可以发现完成一个请求时三个人中必然有一人在这个请求的位置,所以我们可以根据请求来判断其中一人的位置,这样我们就只需要记录其他两个人了。而复杂度似乎刚好够用。
设 $ F[i][j][k] $ 表示已经处理完第 $ i $ 个请求,且另外两个人分别在 $ j $ 和 $ k $ 的的最小花费,然后我们可以用这个状态向后转移:
if(j!=a[i+1]&&k!=a[i+1])f[i+1][j][k]=min(f[i+1][j][k],f[i][j][k]+d[a[i]][a[i+1]]);
if(a[i]!=a[i+1]&&k!=a[i+1])f[i+1][a[i]][k]=min(f[i+1][a[i]][k],f[i][j][k]+d[j][a[i+1]]);
if(a[i]!=a[i+1]&&j!=a[i+1])f[i+1][a[i]][j]=min(f[i+1][a[i]][j],f[i][j][k]+d[k][a[i+1]]);
需要注意题目说了不能有两个人在同一个位置!
$ code: $
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int
using namespace std;
int m,n,ans;
int a[1005];
int d[205][205];
int f[1003][203][203];
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar())) if(ch=='-')sign=1;
while(isdigit(ch)) res=res*10+(ch^48),ch=getchar();
return sign?-res:res;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
m=qr(); n=qr(); a[0]=1;
for(rg i=1;i<=m;++i)
for(rg j=1;j<=m;++j)
d[i][j]=qr();
for(rg i=1;i<=n;++i) a[i]=qr();
for(rg i=0;i<=n;++i)
for(rg j=1;j<=m;++j)
for(rg k=1;k<=m;++k)
f[i][j][k]=1e7;
f[0][2][3]=0;
for(rg i=0;i<n;++i){
for(rg j=1;j<=m;++j){
for(rg k=1;k<=m;++k){
if(f[i][j][k]<1e7){
if(j!=a[i+1]&&k!=a[i+1])f[i+1][j][k]=min(f[i+1][j][k],f[i][j][k]+d[a[i]][a[i+1]]);
if(a[i]!=a[i+1]&&k!=a[i+1])f[i+1][a[i]][k]=min(f[i+1][a[i]][k],f[i][j][k]+d[j][a[i+1]]);
if(a[i]!=a[i+1]&&j!=a[i+1])f[i+1][a[i]][j]=min(f[i+1][a[i]][j],f[i][j][k]+d[k][a[i+1]]);
}
}
}
} ans=1e7;
for(rg i=1;i<=m;++i)
for(rg j=1;j<=m;++j)
ans=min(ans,f[n][i][j]);
printf("%d\n",ans);
return 0;
}
最新文章
- JVM垃圾回收(GC)原理
- Group Anagrams
- HttpWatch网络抓包工具的使用
- Call Azure Queue get ";The remote server returned an error: (400) Bad Request.";
- javascript中神奇的(+)加操作符
- 如何获取启动文件路径 GetModuleFileName
- Spring 容器可以在自动装配相互协作的 bean 之间的关系,使用autowire属性定义指定自动装配模式。
- 【小练习06】HTML+CSS--教学大讲堂
- centos7 安装 oh my zsh
- 查看SQL Server的版本及License
- Java微信二次开发(八)
- ubuntu eclipse 无法打开
- backdoor-factory
- 【AtCoder】Dwango Programming Contest V题解
- mysql如何优化插入记录速度
- IE7下对某些seajs压缩文件不兼容的解决方法
- Redis偶发连接失败案例分析
- vue短信验证性能优化写入localstorage中
- python 列表排序方法reverse、sort、sorted基础篇
- Java代码签名证书申请和使用指南
热门文章
- AS创建工程结构
- POJ——1364King(差分约束SPFA判负环+前向星)
- [luoguP3317] [SDOI2014]重建(矩阵树定理)
- NOJ1203 最多约数问题 [搜索 数论]
- Python入门--6--今天抄袭人家一篇日志--numpy这个
- Delphi中的操作二进制文件的两个重要函数
- (25)python urllib库
- ubuntu安装软件或upgrade出现 You might want to run &#39;apt-get -f install&#39; to correct these
- Spring注入内部的Beans
- Redhat 5 无法安装elfutils-libelf-devel-0.137问题