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 intusing 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; }

轉載于:https://www.cnblogs.com/812-xiao-wen/p/11007705.html

總結

以上是生活随笔為你收集整理的CH 5102 Mobile Service（线性DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。