正題

題目鏈接:http://www.joyoi.cn/problem/tyvj-1061

---

題目大意

有n個(gè)點(diǎn)，每個(gè)點(diǎn)之間都有權(quán)值不同的邊，有3個(gè)機(jī)器人，有m個(gè)任務(wù)地點(diǎn)，機(jī)器人必須按順序趕到任務(wù)地點(diǎn)，求最小代價(jià)。

---

解題思路

我們可以讓fi,jfi,j表示兩個(gè)機(jī)器人在i和j，另外一個(gè)在上一個(gè)任務(wù)地點(diǎn)，然后動(dòng)態(tài)轉(zhuǎn)移就是讓3個(gè)機(jī)器人任意一個(gè)去任務(wù)地點(diǎn)。
動(dòng)態(tài)轉(zhuǎn)移方程

f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+dis[p[i]][p[i+1]]);f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+dis[p[i]][p[i+1]]);

f[i+1][p[i]][y]=min(f[i+1][p[i]][y],f[i][x][y]+dis[x][p[i+1]]);f[i+1][p[i]][y]=min(f[i+1][p[i]][y],f[i][x][y]+dis[x][p[i+1]]);

f[i+1][x][p[i]]=min(f[i+1][x][p[i]],f[i][x][y]+dis[y][p[i+1]]);f[i+1][x][p[i]]=min(f[i+1][x][p[i]],f[i][x][y]+dis[y][p[i+1]]);

---

code

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,dis[201][201],f[2][201][201],ans,p[1001],l,r; int main() {scanf("%d%d",&n,&l);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&dis[i][j]);for(int i=1;i<=l;i++) scanf("%d",&p[i]);memset(f,127/3,sizeof(f));f[0][1][2]=0;p[0]=3;for(int i=0;i<l;i++){r^=1;//壓縮數(shù)組for(int x=1;x<=n;x++)for(int y=1;y<=n;y++)f[r][x][y]=2147483647/3;for(int x=1;x<=n;x++)for(int y=1;y<=n;y++){f[r][x][y]=min(f[r][x][y],f[r^1][x][y]+dis[p[i]][p[i+1]]);f[r][p[i]][y]=min(f[r][p[i]][y],f[r^1][x][y]+dis[x][p[i+1]]);f[r][x][p[i]]=min(f[r][x][p[i]],f[r^1][x][y]+dis[y][p[i+1]]);//動(dòng)態(tài)轉(zhuǎn)移}}ans=2147483647;for(int x=1;x<=n;x++)for(int y=1;y<=n;y++)ans=min(ans,f[r][x][y]);//統(tǒng)計(jì)答案printf("%d",ans); }

總結(jié)

以上是生活随笔為你收集整理的JoyOI(TYVJ)1061-Mobile Service【线性dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。