目錄

今天知識點(diǎn)

dp每個票的使用情況，然后更新此票狀態(tài)下的最優(yōu)解，dp到?jīng)]有票就行了

dp每行的種植狀態(tài)，從i-1行進(jìn)行不斷轉(zhuǎn)移

dp每行的種植狀態(tài)，從i-1和i-2行進(jìn)行不斷轉(zhuǎn)移

POJ2686馬車旅行

思路：

POJ3254 玉米田

思路：

POJ1185：炮兵陣地

思路：

---

????????

????????

前置知識：

基于狀態(tài)壓縮下的集合操作：
1.空集:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?0

2.只含有第i個元素的集合{i}:? ? ? ? ? ? ? ? ? ? ? ? ? 1<<i

3.含有全部n個元素的集合{0,1,2,....,n-1}:??(1<<n)-1

4.判斷第i個元素是否屬于集合S:? ? ? ? ? ??if(S>>i&1)

5.向集合中加入第i個元素S ∪ {i}:? ? ? ? ? ? ? ??S|1<<i

6.從集合中除去第i個元素S -?{i}:? ? ? ? ? ??S&~(1<<i)

7.集合S和T的并集S∪T:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?S | T

8.集合S和T的交集S∩T:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??S & T

????????

????????

POJ2686馬車旅行

有一個公路網(wǎng)連接這些城市，可以乘坐馬車通行。乘坐馬車需要一張票，旅行者有許多車票，每張票上都標(biāo)記了馬的數(shù)量，馬越多跑的越快。
你應(yīng)該考慮如果使用這些票使得在最短時間內(nèi)把旅行者從出發(fā)點(diǎn)他帶到目的地的最佳路線。
假設(shè)一下條件：
1.通過公路直接連接的兩個城市之間只能使用一張車票，且每張票只能用一次
2.乘馬車的時間等于兩城市之間的距離除以馬的數(shù)量
3.忽略換乘所需的時間

輸入：
2 4 4 2 1
3 1
2 3 3
1 3 3
4 1 2
4 2 5
2 4 3 4 1
5 5
1 2 10
2 3 10
3 4 10
輸出：
3.667
impossible

????????

思路：

因?yàn)槊颗芤淮纹钡臓顟B(tài)就變動一次，所以我們設(shè)置dp[s][u]表示達(dá)到當(dāng)前u點(diǎn)且持有s車票的最小花費(fèi)，其中s是票的二進(jìn)制狀態(tài)。

????????

狀態(tài)轉(zhuǎn)移：從u到v，當(dāng)前點(diǎn)v的狀態(tài)s一定最小的dp[s'][u]+dis/t轉(zhuǎn)移過來（其中s=s'&~(1<<i)）

????????
dp[s&~(1<<i)][v]=min(dp[s&~(1<<i)][v],dp[s][u]+dis[u][v]/t[i]) ?

????????
轉(zhuǎn)移順序：s從大到小，因?yàn)榇蟮臓顟B(tài)必須要先于小的先確定下來，所以s一定在最外層。然后是每個起點(diǎn)到每個終點(diǎn)使用每張票來去更新每個點(diǎn)，也就是維護(hù)該狀態(tài)下的最優(yōu)解
????????

#include <bits/stdc++.h>
using namespace std;
const double inf=0x3f3f3f3f;
double ans;
int n,m,p,a,b;
int t[20],dis[50][50];
double dp[1<<10][32];//dp[s][u]表示達(dá)到當(dāng)前u點(diǎn)且持有s車票的最小花費(fèi)void solve(){for(int i=0;i<(1<<(n+1));i++)for(int j=0;j<=m+1;j++)dp[i][j]=inf;dp[(1<<n)-1][a]=0;//起點(diǎn)狀態(tài)ans=inf;for(int s=(1<<n)-1;s>=0;s--){//狀態(tài)從大到小for(int u=1;u<=m;u++)//遍歷每個城市for(int i=0;i<n;i++)//遍歷每種車票可用就用if((s>>i)&1)for(int v=1;v<=m;v++)//尾點(diǎn)城市if(dis[u][v]>=0){//如果能走，就把第i張票置零dp[s&~(1<<i)][v]=min(dp[s&~(1<<i)][v],dp[s][u]+(double)dis[u][v]/t[i]);}ans=min(ans,dp[s][b]);}} 
int main(){while(cin>>n>>m>>p>>a>>b){if(n+m+p+a+b==0)break;for(int i=0;i<n;i++){scanf("%d",&t[i]);//每張車票的數(shù)量}memset(dis,-1,sizeof(dis));//初始化成無窮大也行for(int i=0;i<p;i++){//p條變int u,v,w;scanf("%d%d%d",&u,&v,&w);dis[u][v]=dis[v][u]=w;}solve();if(ans==inf)printf("Impossible\n");else printf("%.3lf\n",ans);}
}

????????

????????

POJ3254 玉米田

由m*n(m<12,n<12)的方格組成的玉米田，要在這些方格上種上玉米，有些方格是貧瘠的(0表示)，有些是肥沃的(1表示)，貧瘠的不能種植。
另外在種植的時候不能在相鄰的方格種上玉米，也就是不能共享邊。問一共有多少種種植方案。

輸入
2 3?
1 1 1
0 1 0

????????

思路：

每一行的狀態(tài)都和上一行的狀態(tài)有關(guān)，狀態(tài)數(shù)有太多因此需要進(jìn)行狀態(tài)壓縮
首先將每行的狀態(tài)壓縮成j的二進(jìn)制狀態(tài)。然后我們進(jìn)行dp行，設(shè)置dp[i][j]表示第i行的第j種狀態(tài)時對應(yīng)的前i行的方案數(shù)。
轉(zhuǎn)移方程：dp[i][j]=(dp[i][j]+dp[i-1][k])%mod; （k是第i-1行所有的可行狀態(tài)）

在確定每行轉(zhuǎn)移的時候都要考慮：
1.橫向方案 ? ?2.橫向方案是否和地圖匹配 ? ? 3.是否和i-1行沖突

????????
存每行的可能狀態(tài)：相鄰的兩列不能都是1，那就看x&x<<1是不是0（就是可能的橫向方案）
是否和i-1沖突：種表示1，不種表示0 那么在判斷兩行合法性時，不能出現(xiàn)有一列同1(兩行都種)，所以x&y=0是合法的
存圖：肥沃我們用0表示，貧瘠用1表示 ?那么判斷此地和此種法合法性時，不能出現(xiàn)同1(在貧瘠的地方種)，所以x&y=0是合法的
（如果不這樣的話0和1與是0，你就分不清了）

????????
【注意】：外面每行i循環(huán)一次，其次里面是第i行的每個狀態(tài)j循環(huán)一次(找到合適的j)，最后是第i-1行的每個狀態(tài)k循環(huán)一次(找到每個合適的k)，共O(n^3)

#include <bits/stdc++.h>
using namespace std;
const int mod=1e8;
int sta[600],top,n,m;
int dp[20][600],cur[20];bool check(int x){if(x&x<<1)return 0;return 1;
} void init(){//預(yù)處理top=0;for(int i=0;i<(1<<n);i++){//記錄所有的沒有相鄰1的種法if(check(i))sta[++top]=i;}
}void solve(){for(int j=1;j<=top;j++){//處理第一行if(!(sta[j]&cur[1])) dp[1][j]=1;}for(int i=2;i<=m;i++){//處理剩余行for(int j=1;j<=top;j++){//sta[j]是第i行的每種種法if(sta[j]&cur[i]) continue;//檢測當(dāng)前狀態(tài)是否和當(dāng)前行匹配for(int k=1;k<=top;k++){//sta[k]是i-1行的每種法if(sta[k]&cur[i-1])continue;//檢測當(dāng)前狀態(tài)和當(dāng)前行是否匹配if(sta[j]&sta[k])continue;//第i行和第i-1行有沖突dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;}}}
}int main(){while(cin>>m>>n){//m是行n是列init();int num;memset(dp,0,sizeof(dp));for(int i=1;i<=m;i++){cur[i]=0;for(int j=1;j<=n;j++){scanf("%d",&num);if(num==0)cur[i]+=(1<<(n-j));//讀入地圖 1變0，0變1}}solve();int ans=0;for(int j=1;j<=top;j++)ans=(ans+dp[m][j])%mod;//最后一行所有方案數(shù)加起來cout<<ans;}
}

????????

????????

????????

POJ1185：炮兵陣地

在N*M(N<100,M<10)的地圖上布置炮兵，H格子為山地不能布置，P格子為平原可以布置。炮兵的攻擊范圍是沿橫向左右各兩格，沿縱向上下個兩格子
炮兵之間不能誤傷。問在整個地圖中最多能拜訪多少個炮兵？
5 4
PHPP
PPHH
PPPP
PHPP
PHHP

????????

思路：

????????
首先要對行進(jìn)行狀態(tài)壓縮(對列的話太大了，枚舉2^100還不如不壓縮呢)，我們每次確定行的狀態(tài)都需要考慮：
1.橫向方案 ? ?2.橫向方案是否和地圖匹配 ? ? 3.是否和i-1行i-2行沖突

設(shè)置dp[i][j][k]表示第i行為第j狀態(tài)，第i-1行為第k狀態(tài)時 對應(yīng)的前i行放置的最大炮兵數(shù)。
轉(zhuǎn)移方程：dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][t]+num[j]);

（j是第i行的方案，k是第i-1行的方案，t是i-2行的方案）

????????
存每行的可能狀態(tài)：左右相鄰1個間隔和2個間隔都不能炮兵（就是可能的橫向方案）
存圖：(1,1)開始存。0表示平原，1表示山地，那么在放置的時候不能出現(xiàn)同1(在山地放炮兵)，所以x&y=0是合法的（保證合法的是0就行了）
是否沖突：第i行和第i-1行，第i-2行 不能出現(xiàn)有一列同1(兩行都放炮兵)，所以x&y=0是合法的

????????
【注意】：外面每行i循環(huán)一次，其次里面是第i行的每個狀態(tài)j循環(huán)一次(找到合適的j)，然后是第i-1行的每個狀態(tài)k循環(huán)一次(供第i行找到合適的k)，
接著是第i-2行的每個狀態(tài)t循環(huán)一次(供第i-1行找到合適的t)

#include <bits/stdc++.h>
using namespace std;
int n,m,top;
char mp[110][20];
int num[70];
int stk[70],cur[70];//stk表示橫向可能的方案，cur是我們存的地圖行
int dp[110][70][70];bool check(int x){if(x&(x<<1))return 0;//相鄰1間隔是否合法if(x&(x<<2))return 0;//相鄰2間隔是否合法return 1;
}void init(){//統(tǒng)計(jì)所有的可能合法狀態(tài)，最多60種top=0;for(int i=0;i<(1<<m);i++){if(check(i))stk[top++]=i;}
}int count(int x){//統(tǒng)計(jì)x二進(jìn)制中1的個數(shù)int cnt=0;while(x){if(x&1)cnt++;x=x>>1;}
//	while(x){//這個更快
//		cnt++;
//		x&=(x-1);
//	}	return cnt;
}int solve(){int ans=0;memset(dp,-1,sizeof(dp));for(int j=0;j<top;j++){//初始化第一行的狀態(tài)num[j]=count(stk[j]);if(!(stk[j]&cur[1])){//和地圖匹配dp[1][j][0]=num[j];//第一行狀態(tài)為j，上一行狀態(tài)為0（知道為啥從(1,1)開始初始化了把）ans=max(ans,dp[1][j][0]);}}for(int i=2;i<=n;i++){//處理每一行for(int j=0;j<top;j++){//遍歷第i行的可能方案if(stk[j]&cur[i])continue;//是否和地圖匹配for(int k=0;k<top;k++){//遍歷第i-1行的可能方案if(stk[j]&stk[k])continue;//此行和上一行是否匹配（不用再判斷和地圖是否匹配，不匹配dp是-1，不影響的）for(int t=0;t<top;t++){//遍歷上二行可能方案if(stk[j]&stk[t])continue;//此行和上二行是否匹配dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][t]+num[j]);}if(i==n)ans=max(ans,dp[i][j][k]);//不要放在外面套3個for取max}}}return ans;
}
int main(){while(cin>>n>>m){init();for(int i=1;i<=n;i++){scanf("%s",mp[i]+1);//加1是為了從1下標(biāo)開始存}for(int i=1;i<=n;i++){cur[i]=0;for(int j=1;j<=m;j++){if(mp[i][j]=='H')//同樣的，不能放的地方存1cur[i]+=(1<<(m-j));}}cout<<solve();}
}