【算法每日一练]-动态规划（保姆级教程篇13）POJ2686马车旅行 #POJ3254 玉米田 #POJ1185：炮兵阵地-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法每日一练]-动态规划（保姆级教程篇13）POJ2686马车旅行 #POJ3254 玉米田 #POJ1185：炮兵阵地。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

今天知识点

dp每个票的使用情况，然后更新此票状态下的最优解，dp到没有票就行了

把状态压缩成j,dp每行i的种植状态，从i-1行进行不断转移

把状态压缩成j,dp每行i的布置状态，从i-1和i-2行进行不断转移

POJ2686马车旅行

思路：

POJ3254 玉米田

思路：

POJ1185：炮兵阵地

思路：

前置知识：

基于状态压缩下的集合操作：
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马车旅行

有一个公路网连接这些城市，可以乘坐马车通行。乘坐马车需要一张票，旅行者有许多车票，每张票上都标记了马的数量，马越多跑的越快。
你应该考虑如果使用这些票使得在最短时间内把旅行者从出发点他带到目的地的最佳路线。
假设一下条件：
1.通过公路直接连接的两个城市之间只能使用一张车票，且每张票只能用一次
2.乘马车的时间等于两城市之间的距离除以马的数量
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

思路：

方程的转移和上一点的票状态有关,且每跑一次票的状态就变动一次，所以每个点的票的状态都会有很多，我们转移的时候还要捎带上状态，所以需要把状态压缩成一维的s。

我们设置dp[s][u]表示达到当前u点且持有s车票的最小花费，其中s是票的二进制状态。

状态转移：从u到v，当前点v的状态s一定由最小的dp[s'][u]+dis/t转移过来（其中s=s'&~(1<<i)）


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


转移顺序：s从大到小，因为大的状态必须要先于小的先确定下来，所以s一定在最外层。然后是每个起点到每个终点使用当前票状态下的每张票，也就是维护该状态下的最优解

#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]表示达到当前u点且持有s车票的最小花费

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;//起点状态
	ans=inf;
	for(int s=(1<<n)-1;s>=0;s--){//状态从大到小
		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++)//尾点城市
					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]);//每张车票的数量
		}
		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

思路：

方程的转移和上一行的状态有关，即每一行i的状态都和上一行i-1的状态有关，因此需要进行状态压缩，即把将每行i的状态压缩成二进制状态j。（如果每行状态和前面所有行状态都有关系，那么就要回溯处理了）
然后我们进行dp行，设置dp[i][j]表示第i行的第j种状态时对应的前i行的方案数。
转移方程：dp[i][j]=(dp[i][j]+dp[i-1][k])%mod; （k是第i-1行所有的可行状态）

在确定每行转移的时候都要考虑：
1.横向方案 2.横向方案是否和地图匹配 3.是否和i-1行冲突

存每行的可能状态：相邻的两列不能都是1，那就看x&x<<1是不是0（就是可能的横向方案）
是否和i-1冲突：种表示1，不种表示0 那么在判断两行合法性时，不能出现有一列同1(两行都种)，所以x&y=0是合法的
存图：肥沃我们用0表示，贫瘠用1表示那么判断此地和此种法合法性时，不能出现同1(在贫瘠的地方种)，所以x&y=0是合法的
（如果不这样的话0和1与是0，你就分不清了）

【注意】：外面每行i循环一次，其次里面是第i行的每个状态j循环一次(找到合适的j)，最后是第i-1行的每个状态k循环一次(找到每个合适的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(){//预处理
	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;//检测当前状态是否和当前行匹配
			for(int k=1;k<=top;k++){//sta[k]是i-1行的每种法
				if(sta[k]&cur[i-1])continue;//检测当前状态和当前行是否匹配
				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;//最后一行所有方案数加起来
		cout<<ans;
	}
}

POJ1185：炮兵阵地

在N*M(N<100,M<10)的地图上布置炮兵，H格子为山地不能布置，P格子为平原可以布置。炮兵的攻击范围是沿横向左右各两格，沿纵向上下个两格子
炮兵之间不能误伤。问在整个地图中最多能拜访多少个炮兵？
5 4
PHPP
PPHH
PPPP
PHPP
PHHP

思路：

方程的转移和上一行的状态有关，但是状态又太多了，故要状态压缩。

首先要对行进行状态压缩(对列的话太大了，枚举2^100还不如不压缩呢)，我们每次确定行的状态都需要考虑：
1.横向方案 2.横向方案是否和地图匹配 3.是否和i-1行i-2行冲突
设置dp[i][j][k]表示第i行为第j状态，第i-1行为第k状态时对应的前i行放置的最大炮兵数。
转移方程：dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][t]+num[j]);

（j是第i行的方案，k是第i-1行的方案，t是i-2行的方案）
存每行的可能状态：左右相邻1个间隔和2个间隔都不能炮兵（就是可能的横向方案）
存图：(1,1)开始存。0表示平原，1表示山地，那么在放置的时候不能出现同1(在山地放炮兵)，所以x&y=0是合法的（保证合法的是0就行了）
是否冲突：第i行和第i-1行，第i-2行不能出现有一列同1(两行都放炮兵)，所以x&y=0是合法的

【注意】：外面每行i循环一次，其次里面是第i行的每个状态j循环一次(找到合适的j)，然后是第i-1行的每个状态k循环一次(供第i行找到合适的k)，
接着是第i-2行的每个状态t循环一次(供第i-1行找到合适的t)文章来源地址https://www.toymoban.com/news/detail-766913.html

#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(){//统计所有的可能合法状态，最多60种
	top=0;
	for(int i=0;i<(1<<m);i++){
		if(check(i))stk[top++]=i;
	}
}

int count(int x){//统计x二进制中1的个数
	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++){//初始化第一行的状态
		num[j]=count(stk[j]);
		if(!(stk[j]&cur[1])){//和地图匹配
			dp[1][j][0]=num[j];//第一行状态为j，上一行状态为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下标开始存
		}
		for(int i=1;i<=n;i++){
			cur[i]=0;
			for(int j=1;j<=m;j++){
				if(mp[i][j]=='H')//同样的，不能放的地方存1
					cur[i]+=(1<<(m-j));
			}
		}
		cout<<solve();
	}
}

到了这里，关于【算法每日一练]-动态规划（保姆级教程篇13）POJ2686马车旅行 #POJ3254 玉米田 #POJ1185：炮兵阵地的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！