題目描述

n個(gè)人在做傳遞物品的游戲,編號(hào)為1-n。

游戲規(guī)則是這樣的：開始時(shí)物品可以在任意一人手上，他可把物品傳遞給其他人中的任意一位；下一個(gè)人可以傳遞給未接過物品的任意一人。

即物品只能經(jīng)過同一個(gè)人一次，而且每次傳遞過程都有一個(gè)代價(jià)；不同的人傳給不同的人的代價(jià)值之間沒有聯(lián)系；

求當(dāng)物品經(jīng)過所有n個(gè)人后，整個(gè)過程的總代價(jià)是多少。

輸入輸出格式

輸入格式：

第一行為n,表示共有n個(gè)人（16>=n>=2）；

以下為n*n的矩陣，第i+1行、第j列表示物品從編號(hào)為i的人傳遞到編號(hào)為j的人所花費(fèi)的代價(jià)，特別的有第i+1行、第i列為-1（因?yàn)槲锲凡荒茏约簜鹘o自己），其他數(shù)據(jù)均為正整數(shù)(<=10000)。

輸出格式：

一個(gè)數(shù)，為最小的代價(jià)總和。

輸入輸出樣例

輸入樣例#1：

2
-1 9794
2724 –1

輸出樣例#1：

2724

思路：狀壓 DP 入門題

每個(gè)人只能被傳遞一次，用一個(gè) n 位二進(jìn)制數(shù)來表示每個(gè)人是否被訪問過，但這無法知道物品在誰手中，因此加一個(gè)狀態(tài)，來表示物品在誰手中。

用 f[i][j] 表示在 i 狀態(tài)時(shí)最后的一個(gè)是 j，初始狀態(tài)為 f[1<<i][i]=0；表示一開始物品在i手中，所求狀態(tài)為 min(f[(1<<n)-1][j]);? 因此有轉(zhuǎn)移方程：f[i][j]=min(f[i-(1<<j)][k]+cost[k][j],f[i][j])?

k 表示從 k 點(diǎn)轉(zhuǎn)移到了 j 位置，所以要求 j、k 都應(yīng)該是集合 i 中的元素

源代碼

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<set> #include<map> #include<stack> #include<ctime> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 10007 #define E 1e-6 #define LL long long using namespace std; LL f[1<<17][20],cost[20][20]; int main() {int n;cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>cost[i][j];/*標(biāo)識(shí)狀態(tài)初始化*/memset(f,127,sizeof(f));for(int i=0;i<n;i++)f[1<<i][i]=0;int cnt=(1<<n)-1;for(int i=1;i<=cnt;i++){for(int j=0;j<n;j++){if(i&(1<<j)){for(int k=0;k<n;k++){if( j!=k && (i&(1<<k)) )//k在狀態(tài)i中不存在{LL x=(i-(1<<j));f[i][j]=min(f[x][k]+cost[k][j],f[i][j]);}}}}}LL minn=INF;for(int i=0;i<n;i++)minn=min(minn,f[cnt][i]);cout<<minn<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的最小总代价（洛谷-U17433）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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