先來一個題銜接一下：

與上一題的思路差不多，不過這里有幾點需要注意：

1.因為某一列的狀態還與上上一行有關，因此我們令f[i][j][k]表示第i行狀態為j,第i-1行狀態為k的最大炮兵數。

因此，我們可以得到狀態轉移方程：f[i][j][k]=max(f[i][j][k],f[i-1][k][q]+num[j])其中我們保證j,k,q不沖突并且自己可以。

2.注意到直接開存不下，我們考慮用vector存符合條件的，并計算一下有幾個再開空間。

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[110],dp[110][70][70];
vector<int> st;
char b;
vector<int> num;
int calc(int num){int ans=0;while(num){if((num&1)==1) ans++;num>>=1;}return ans;
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf(" %c",&b);if(b=='H'){a[i]|=(1<<(j-1));}}}for(int i=0;i<=(1<<m)-1;i++){if(i&(i<<1)) continue;if(i&(i<<2)) continue;st.push_back(i);num.push_back(calc(i));}int ans=0;for(int i=1;i<=n;i++){for(int j=0;j<st.size();j++){if((a[i]&st[j])) continue;for(int k=0;k<st.size();k++){if((a[i-1]&st[k])) continue;if((st[k]&st[j])) continue;for(int q=0;q<st.size();q++){if(i>=2){if((a[i-2]&st[q])) continue;}if((st[k]&st[q])) continue;if((st[q]&st[j])) continue;dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][q]+num[j]);ans=max(ans,dp[i][j][k]);}}}}cout<<ans;
}

首先，什么是TSP問題？

即給你一張抽象的圖，求從某一個起點出發，經過所有點的最短路徑。

如何解決呢？

我們先建立一個超級源點，這就解決了從某一個起點出發的問題，然后，我們假設走了134，現在在5，那么后來的267是與134的走法無關的，因此我們只要保留最短的即可，即DP。

因此，我們可以令f[st][i]表示當前狀態為st,最后到達的一個點為i所經過的最短路徑。

訪問過標1，未訪問標0.

轉移方程為f[st][i]=min(f[st'][j]+a[j][i]).（st'=st-1<<(i-1)).

若為必須回到原點，那么走出來的一定是一個圈，因此我們固定1為起點，然后在原來的結果上加上終點與1的邊。

下面是實現代碼：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[25][25],dp[1<<20][25];
int f(int st,int x){if(dp[st][x]<=1e9){return dp[st][x];}int stt=st-(1<<(x-1));for(int i=1;i<=n;i++){if(a[i][x]==0) continue;if((stt>>(i-1))&1){dp[st][x]=min(dp[st][x],a[i][x]+f(stt,i));}}return dp[st][x];
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;a[x][y]=z;a[y][x]=z;}memset(dp,0x7f,sizeof(dp));dp[1][1]=0;int ans=0x7f7f7f7f;int st=(1<<n)-1;for(int i=2;i<=n;i++){int tmp=f(st,i);if(a[i][1]!=0) ans=min(ans,a[i][1]+tmp);}cout<<ans;
} 

我們來看一個類似的問題：

思路類似，我們令f[i]表示狀態為i時獲得的最大能量。

其中第k位==1表示它已經用了并消失，為0表示沒有用或用了沒消失。

易得狀態轉移方程：f[k|(1<<(i-1)]=max(f[k]+a[j][i]).我們轉換一下：

f[k]=max(f[k']+a[j][i])(其中k'的i與j位為0，k=k'+1<<(i-1))

下面是AC代碼：

#include<bits/stdc++.h>
using namespace std;
int n,a[14][14],x,f[2000];
int main(){while(cin>>n){memset(f,0,sizeof(f));if(n==0) break;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&x);a[i][j]=x;}}int ans=0;for(int i=1;i<=(1<<n)-2;i++){for(int k=0;k<i;k++){for(int ii=1;ii<=n;ii++){if((k>>(ii-1))&1) continue;for(int jj=1;jj<=n;jj++){if((k>>(jj-1))&1) continue;if(i!=(k|(1<<(jj-1)))) continue;f[i]=max(f[i],f[k]+a[ii][jj]);ans=max(ans,f[i]);}}}}printf("%d\n",ans);}
}