week11-复习floyd，01背包求方案数，01背包可行性判断，动态规划

1.汤姆斯的天堂梦

题目描述

汤姆斯生活在一个等级为 0 的星球上。那里的环境极其恶劣，每天 12 小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为 N 的星球上天堂般的生活。

有一些航班将人从低等级的星球送上高一级的星球，有时需要向驾驶员支付一定金额的费用，有时却又可以得到一定的金钱。

汤姆斯预先知道了从 0 等级星球去 N 等级星球所有的航线和需要支付（或者可以得到）的金钱，他想寻找一条价格最低（甚至获得金钱最多）的航线。

输入格式

第一行一个正整数 N（N < 100），接下来的数据可分为 N 个段落，每段的第一行一个整数 K_i（K_i < 100），表示等级为 i 的星球有 K_i 个。

接下来的 K_i 行中第 j 行依次表示与等级为 i，编号为 j 的星球相连的等级为 i - 1 的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过 1000）。

每行以 0 结束，每行的航线数 < 100。

输出格式

输出所需（或所得）费用。正数表示支出，负数表示收益。

样例 #1

样例输入 #1

3
2
1 15 0
1 5 0
3
1 -5 2 10 0
1 3 0
2 40 0
2
1 1 2 5 3 -5 0
2 -19 3 -20 0

样例输出 #1

-1

提示

对于 100 % 的数据，1 < N < 100，1 < K_i < 100。

样例解释：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jEsrAJg0-1673855085919)(C:\Users\zc\Desktop\补题题解\img\652.png)]

显然，这是一道动态规划的问题，我们可以假设 f(i,j) 为到达等级为 i 的第 j 个星球所需要的最小费用。那么我们就可以很容易的写出它的转台转移方程：
f ( i , j ) = m i n ( f ( i , j ) , f ( i − 1 , t ) a t ) 1 ≤ t ≤ k f(i,j)=min(f(i,j),f(i-1,t) a_t)\quad 1\leq t \leq k f(i,j)=min(f(i,j),f(i−1,t) at)1≤t≤k
其中，a_t表示从等级为 i-1 的第 t 个星球到等级为 i 的第 j 个星球所需要的代价， k 表示等级为 i-1 的星球最多有 k 个。

所以知道了状态转移方程后，我们就需要确定初始状态，初始状态就是到等级不为0的星球所需费用为无穷大（因为都还没到，所以就到不了，所以费用应该是无穷大）。我们只需要定义一个无穷大的值就行了。

当然，我不知道有没有和我一样的，这个输入方式是真的好绕，我看了好久才看懂这是怎么输入的QWQ。

话不多说，完整注释代码如下：

#include<bits/stdc  .h>
using namespace std;
#define INF 0xfffffff
int N,K,f[105][105]; //f[i][j]表示到达等级为i的第j个星球所需的最小费用
int main(){
	cin>>N;
	int a,w,b;
	for(int i=1;i<=N;i  ){
		for(int a=0;a<=N;a  ){
			f[i][a]=INF;  //记得初始化
		}
	}
	for(int i=1;i<=N;i  ){  //好绕的输入方式QWQ
		cin>>K;  //代表等级为i的星球有K个
		for(int a=1;a<=K;a  ){
			cin>>b;  //表示i-1级星球中的第b个星球
			while(b!=0){
				cin>>w;  //代表从i-1级星球中的第b个星球到达等级为i的第a个星球所需代价
				f[i][a]=min(f[i-1][b] w,f[i][a]);  //取最小值
				cin>>b;
			}
		}
	}
	int minn=INF;
	for(int i=1;i<=K;i  ){
		minn=min(minn,f[N][i]);  //在等级为N的星球中取最小值
	}
	cout<<minn;
	return 0;
}

2.跑步

题目描述

路人甲准备跑 n 圈来锻炼自己的身体，他准备分多次(>1）跑完，每次都跑正整数圈，然后休息下再继续跑。

为了有效地提高自己的体能，他决定每次跑的圈数都必须比上次跑的多。

可以假设他刚开始跑了 0 圈，那么请问他可以有多少种跑完这 n 圈的方案？

输入格式

一行一个整数，代表 n。

输出格式

一个整数表示跑完这 n 圈的方案数。

样例 #1

样例输入 #1

212

样例输出 #1

995645335

提示

数据规模与约定

对于 100% 的数据，保证 5< n< 500。

刚看到这道题目，我真的一点思路都没有，还是在看了题解后才恍然大悟：这竟然是个01背包问题！

然后我仔细一想，好像确实是01背包。

题目要求每次跑的圈数都比上次多，并且要刚好跑完 n 圈。那么我们其实可以把总圈数想象成容量为 n 的背包，把每次跑的圈数想象成重量为该圈数的物品，因为每次跑的圈数都要比上次多，所以一个物品只能取一次，那么这就是一道求01背包恰好装满背包的方案数的问题了。~~（真是太妙了啊_）~

那么，我们知道了这么多，我们该怎么求呢？

首先，我们先回顾一下01背包问题的状态转移方程（先设 f(i,j) 为在前i件物品，容量为 j 的背包能得到的最大价值） ：
f ( i , j ) = { f ( i − 1 , j ) w ( i ) > j m a x ( f ( i − 1 , j ) , f ( i − 1 , j ) ( i ) ) w ( i ) ≤ j f(i,j)= \begin{cases} f(i-1,j) \quad w(i)>j \\ max(f(i-1,j),f(i-1,j) (i)) \quad w(i)\leq j \end{cases} f(i,j)={f(i−1,j)w(i)>jmax(f(i−1,j),f(i−1,j) (i))w(i)≤j
那么我们也可以仿造这个方程，写出求方案数的状态转移方程。

我们可以设 f(i,j) 表示在前i件物品中装满容量为 j 的背包所有的方案数。那么我们对于每一样物品也只有装和不装的选择，那么，它的转态转移方程也就为：
f ( i , j ) = { f ( i − 1 , j ) w ( i ) > j ( 只能不装 ) f ( i − 1 , j ) f ( i − 1 , j − w ( i ) ) w ( i ) ≤ j ( 选择不装与装的方案数之和 ) f(i,j)= \begin{cases} f(i-1,j) \quad w(i)>j \quad(只能不装)\\ f(i-1,j) f(i-1,j-w(i)) \quad w(i) \leq j \quad (选择不装与装的方案数之和) \end{cases} f(i,j)={f(i−1,j)w(i)>j(只能不装)f(i−1,j) f(i−1,j−w(i))w(i)≤j(选择不装与装的方案数之和)
所以，我们就可以将这道题转化为01背包求解方案数的问题了：我们设 f(i,j) 表示跑 在前 i 个圈数中选择，刚好跑 j 圈的总的方案数。（前 i 个圈数分别为 1~i ,因为每一次跑的圈数都要比上次多），转态转移方程跟上面一样，我们最后要求的也就是 f(n,n) 了。

话不多说，完整注释代码如下：

#include<bits/stdc  .h>
using namespace std;
long long dp[505][505],n,w[505];
int main(){
	dp[0][0]=1; //记得初始化
	cin>>n;
	for(int i=1;i<=n;i  ){
		w[i]=i;  //圈数也要初始化
	}
	for(int i=1;i<=n;i  ){
		for(int a=0;a<=n;a  ){
			if(w[i]>a){
				dp[i][a]=dp[i-1][a];  
			}
			else{
				dp[i][a]=dp[i-1][a] dp[i-1][a-w[i]];  //DP
			}
		}
	}
	int ans=0;
	cout<<dp[n][n]-1;  //要减1是因为不能一次跑完
    return 0;
}

3.[蓝桥杯 2021 省 AB] 砝码称重

题目描述

你有一架天平和 N 个砝码, 这 N 个砝码重量依次是 W_1, W_2, …, W_N 。 请你计算一共可以称出多少种不同的重量?

注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N 。

第二行包含 N 个整数: W_1, W_2, W_3, …, W_N 。

输出格式

输出一个整数代表答案。

样例 #1

样例输入 #1

3
1 4 6

样例输出 #1

10

提示

【样例说明】

能称出的 10 种重量是: 1 、 2 、 3 、 4 、 5 、 6 、 7 、 9 、 10 、 11 。

1 = 1 2 = 6 − 4 (  天平一边放  6 ,  另一边放 4)  3 = 4 − 1 4 = 4 5 = 6 − 1 6 = 6 7 = 1 6 9 = 4 6 − 1 10 = 4 6 11 = 1 4 6 \begin{aligned} &1=1 \\ &2=6-4(\text { 天平一边放 } 6, \text { 另一边放 4) } \\ &3=4-1 \\ &4=4 \\ &5=6-1 \\ &6=6 \\ &7=1 6 \\ &9=4 6-1 \\ &10=4 6 \\ &11=1 4 6 \end{aligned} 1=12=6−4( 天平一边放 6, 另一边放 4) 3=4−14=45=6−16=67=1 69=4 6−110=4 611=1 4 6

【评测用例规模与约定】

对于 50 % 的评测用例, 1 <= N <= 15 。

对于所有评测用例, 1 <= N <= 100, N 个砝码总重不超过 10^5。

蓝桥杯 2021 第一轮省赛 A 组 F 题（B 组 G 题）。

又是一道动态规划的问题，但是是一道判断可行性的问题，也就是01背包判断可行性的问题。我们可以设 f(i) 表示重量为 i 是否可以称出。1表示可以，0表示不行。那么我们该怎么写出状态转移方程呢？

在这里我引用洛谷题解里的这位大佬的话解释一下：

• 为了转移，f(0)=1，什么都不放时，重量为 0，因此可以称出。

那么枚举 f(1)~f(sum) (sum为砝码可以称得的最大重量)

• 如果 j-w可以称出，且重量为 w 的砝码存在，则 j可以称出。即 f(j-w)=f(j)

因为这里的砝码可以放两端，所以我们要反着再遍历一遍就可以了。

当然，你也可以通过01背包的思想去做。对一个砝码，我可以有3个选择，不放，放左边和放右边的选择，并以此来做也是可以的，在这里不过多赘述。

完整代码如下：

#include<bits/stdc  .h>
using namespace std;
int n,f[105],dp[1000005];
int main(){
	cin>>n;
	int k,sum=0,ans=0;
	for(int i=1;i<=n;i  ){
		cin>>k;
		sum =k;  //记录sum
		f[i]=k;  //记录砝码重量
	}
	dp[0]=1;
	for(int i=1;i<=n;i  ){
		for(int a=sum;a>=0;a--){   
			if(a-f[i]>=0&&!dp[a]&&dp[a-f[i]]){  //如果在条件符合的情况下,a-f(i)可以称，且存在f(i)，那么代表a也可以称
				dp[a]=1,ans  ;     //记录答案
			}
		}
	}
	for(int i=1;i<=n;i  ){
		for(int a=0;a<=sum;a  ){
			if(a f[i]<=sum&&!dp[a]&&dp[a f[i]]){  //同上
				dp[a]=1,ans  ;
			}
		}
	}
	cout<<ans;
    return 0;
}

4.遗址

题目描述

很久很久以前有一座寺庙，从上往下看寺庙的形状正好是一个正方形，由 4 个角上竖立的圆柱搭建而成。现在圆柱都倒塌了，只在地上留下圆形的痕迹，可是现在地上有很多这样的痕迹，专家说一定是最大的那个。

写一个程序，给出圆柱的坐标，找出由 4 个圆柱构成的最大的正方形，因为这就是寺庙的位置，要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。

例如图有 10 根柱子，其中 (4,2),(5,2),(5,3),(4,3) 可以形成一个正方形，(1,1),(4,0),(5,3),(2,4) 也可以，后者是其中最大的，面积为 10。

输入格式

第一行包含一个 N(1<=N<= 3000)，表示柱子的数量。

接下来 N 行，每行有两个空格隔开的整数表示柱子的坐标（坐标值在 0 到 5000 之间），柱子的位置互不相同。

输出格式

如果存在正方形，输出最大的面积，否则输出 0。

样例 #1

样例输入 #1

10
 9 4
 4 3
 1 1
 4 2
 2 4
 5 8
 4 0
 5 3
 0 5
 5 2

样例输出 #1

10

提示

【数据范围】

30% 满足：1<= N <=100。

60% 满足：1<= N <= 500。

100% 满足：1<= N <= 3000。

这道题的难点就在于我们该怎么确定一个正方形。如果我们想通过确定3个点找另一个点的位置，或者直接确定4个点的位置的方法来确定正方形，那么这道题最多3000的数据，以及这种方法带来的 O（n^3）甚至 O（n^4 ）的光速，肯定是会TLE的，那么我们要想办法降低时间复杂度。我们如果可以通过确定两个点来确定正方形的话，那么就可以将时间复杂度降低至O（n^2）,那么就可以了。那么我们该怎么通过两个点确定正方形呢？

在这里，我引用洛谷题解里的这位大佬的话来解释：

如图所示，我们将左上顶点定为 i，左下顶点对应 j，那么可以发现如下关系：

1. 标红段为 i 与 j的横坐标差，正好为左下顶点与右下顶点的纵坐标之差。
2. 标蓝段为 i与 j 的纵坐标差，正好为左下顶点与右下顶点的横坐标之差。

如此，我们即可仅仅通过两个点推出其余两个点的坐标。

所以，求面积我们也就是求边长的平方就可以了，通过我们初中（应该吧）就学过的勾股定理就可以轻松求出了。

完整注释代码如下：

#include<bits/stdc  .h>
using namespace std;
int xarr[3005],yarr[3005];
bool book[5005][5005];  //用一个二维数组标记,例如book[i][j]=1表示点（i,j）存在，=0表示不存在
int n;
int maxx;
void dfs(){	
	int nowx1,nowx2,nowy1,nowy2,to_x1,to_y1,to_x2,to_y2;
	int S;
	for(int i=1;i<=n;i  ){
		nowx1=xarr[i],nowy1=yarr[i];   //表示x1,y1
		for(int a=1;a<=n;a  ){  //两层循环，确定两个点
			nowx2=xarr[a],nowy2=yarr[a];	//表示x2,y2
			to_x1=nowy1-nowy2 nowx1;
			to_y1=nowx2-nowx1 nowy1;
			to_x2=nowy1-nowy2 nowx2;
			to_y2=nowx2-nowx1 nowy2;  //确定其他两个点的坐标
			if(to_x1<0||to_x1>5000||to_y1<0||to_y1>5000||to_x2<0||to_x2>5000||to_y2<0||to_y2>5000){  //要在合法范围内
				continue;
			}
			else{
				if(book[to_x1][to_y1]&&book[to_x2][to_y2]){  //如果两个点都存在，就代表这个正方形存在
					S=pow(nowx1-nowx2,2) pow(nowy1-nowy2,2);
					maxx=max(maxx,S);						 //记录最大面积
				}
			}
		}
	}
}
int main(){
	int x,y;
	cin>>n;
	for(int i=1;i<=n;i  ){
		cin>>x>>y;
		book[x][y]=1;  //标记
		xarr[i]=x;  //记录横坐标
		yarr[i]=y;  //记录纵坐标
	}
	dfs();
	cout<<maxx;  
    return 0;
}

5.[蓝桥杯 2022 国 A] 环境治理

题目描述

LQ 国拥有 n 个城市，从 0 到 n - 1 编号，这 n 个城市两两之间都有且仅有一条双向道路连接，这意味着任意两个城市之间都是可达的。每条道路都有一个属性 D，表示这条道路的灰尘度。当从一个城市 A 前往另一个城市 B 时，可能存在多条路线，每条路线的灰尘度定义为这条路线所经过的所有道路的灰尘度之和，LQ 国的人都很讨厌灰尘，所以他们总会优先选择灰尘度最小的路线。

LQ 国很看重居民的出行环境，他们用一个指标 P 来衡量 LQ 国的出行环境，P 定义为：

P=\sum \limits_{i=0}^{n-1} \sum \limits_{j=0}^{n-1} d(i,j)

其中 d(i,j) 表示城市 i 到城市 j 之间灰尘度最小的路线对应的灰尘度的值。

为了改善出行环境，每个城市都要有所作为，当某个城市进行道路改善时，会将与这个城市直接相连的所有道路的灰尘度都减少 1，但每条道路都有一个灰尘度的下限值 L，当灰尘度达到道路的下限值时，无论再怎么改善，道路的灰尘度也不会再减小了。

具体的计划是这样的：

• 第 1 天，0 号城市对与其直接相连的道路环境进行改善；
• 第 2 天，1 号城市对与其直接相连的道路环境进行改善；

……

• 第 n 天，n - 1 号城市对与其直接相连的道路环境进行改善；
• 第 n 1 天，0 号城市对与其直接相连的道路环境进行改善；
• 第 n 2 天，1 号城市对与其直接相连的道路环境进行改善；

……

LQ 国想要使得 P 指标满足 P <= Q。请问最少要经过多少天之后，P 指标可以满足 P <= Q。如果在初始时就已经满足条件，则输出 0；如果永远不可能满足，则输出 -1。

输入格式

输入的第一行包含两个整数 n, Q，用一个空格分隔，分别表示城市个数和期望达到的 P 指标。

接下来 n 行，每行包含 n 个整数，相邻两个整数之间用一个空格分隔，其中第 i 行第 j 列的值 D_{i,j} (D_{i,j}=D_{j,i},D_{i,i} = 0) 表示城市 i 与城市 j 之间直接相连的那条道路的灰尘度。

接下来 n 行，每行包含 n 个整数，相邻两个整数之间用一个空格分隔，其中第 i 行第 j 列的值 L_{i,j} (L_{i,j} = L_{j,i}, L_{i,i} = 0) 表示城市 i 与城市 j 之间直接相连的那条道路的灰尘度的下限值。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

3 10
0 2 4
2 0 1
4 1 0
0 2 2
2 0 0
2 0 0

样例输出 #1

2

提示

【样例说明】

初始时的图如下所示，每条边上的数字表示这条道路的灰尘度：

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

• d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3；
• d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1；
• d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0。

初始时的 P 指标为 (2 3 1) *2 = 12，不满足 P <= Q = 10;

第一天，0 号城市进行道路改善，改善后的图示如下：

注意到边 (0, 2) 的值减小了 1，但 (0, 1) 并没有减小，因为 L_{0,1} = 2 ，所以 (0, 1) 的值不可以再减小了。此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

• d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 3，
• d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 1，
• d(2, 0) = 3, d(2, 1) = 1, d(2, 2) = 0。

此时 P 仍为 12。

第二天，1 号城市进行道路改善，改善后的图示如下：

此时每对顶点之间的灰尘度最小的路线对应的灰尘度为：

• d(0, 0) = 0, d(0, 1) = 2, d(0, 2) = 2，
• d(1, 0) = 2, d(1, 1) = 0, d(1, 2) = 0，
• d(2, 0) = 2, d(2, 1) = 0, d(2, 2) = 0。

此时的 P 指标为 (2 2) * 2 = 8 < Q，此时已经满足条件。

所以答案是 2。

【评测用例规模与约定】

• 对于 30% 的评测用例，1 <= n <= 10，0 <= L_{i,j} <= D_{i,j} <= 10；
• 对于 60% 的评测用例，1 <= n <= 50，0 <= L_{i,j} <= D_{i,j} <= 10^5；
• 对于所有评测用例，1 <= n <= 100，0 <= L_{i,j} <= D_{i,j} <= 10^5，0 <= Q <= 2^{31} - 1。

蓝桥杯 2022 国赛 A 组 F 题。

显然这是一道多源最短路的题目，我们要用的就是floyd算法了。然后，因为每一次的道路改善，P值必定是减少的，具有单调性，所以我们可以通过二分答案方式来确定答案。那我们的程序要做的也就是对每一次的天数，先模拟进行道路清理（记住减到下限值后就不能再减了），然后跑一次floyd算法来算出新的P值，并与Q值进行对比。floyd算法的时间复杂度是O（n^{3），二分搜索是O(logK)，K表示最大的道路清理的次数。我们可设为10}7。最后的时间复杂度也就为O(n^3logK),可以通过本题。

需要注意的是，我们在模拟道路清理时对于每个城市不能像题目所给的那样一次一次的清理，对应每座城市一次清理完就行了。

还有就是我们要对最开始和全部道路都达到下限值的情况先做一次floyd算法，看看是不是一开始就达到指标以及是否永远都达不到指标。

（我还想说一句：题目真的又臭又长！！！）

完整注释代码如下：

#include<bits/stdc  .h>
using namespace std;
#define maxx 10000001  //定义最大值
int g[105][105],n,q,low[105][105],g_copy[105][105],low_copy[105][105];    //g[][[]存储一开始的图，用g_copy[][]储存清理后的图，low[][]和low_copy[][]存储下限值
int searchans(int l,int r){  //二分答案
	int num,e,ans=0,mid;
	while(l!=r-1){  //二分终止条件
		ans=0;
		mid=(l r)/2;
		num=mid/n,e=mid%n;  //num为第e~n-1号城市清理的次数，num 1为0~e-1号城市清理次数
		for(int i=0;i<e;i  ){
			for(int a=0;a<n;a  ){
				if(i==a){
					continue;
				}
				g_copy[i][a]=g_copy[a][i]=(g[a][i]-num-1);//模拟道路清理
				if(g_copy[i][a]<low[i][a]){
					g_copy[i][a]=g_copy[a][i]=low[i][a];  //不要低于下限值
				}
			}
		}
		for(int i=e;i<n;i  ){
			for(int a=0;a<n;a  ){
				if(i==a){
					continue;
				}
				g_copy[i][a]=g_copy[a][i]=(g[a][i]-num);
				if(g_copy[i][a]<low[i][a]){
					g_copy[i][a]=g_copy[a][i]=low[i][a];   //同上
				}
			}
		}
		for(int i=0;i<n;i  ){
			for(int a=0;a<n;a  ){
				for(int b=0;b<n;b  ){
					g_copy[a][b]=min(g_copy[a][b],g_copy[a][i] g_copy[i][b]);  //floyd算法
				}
			}
		}
		for(int i=0;i<n-1;i  ){
			for(int a=i 1;a<n;a  ){
				ans =g_copy[i][a];  //计算P值
			}
		}				
		ans*=2;  //记得*2
		if(ans<q){
			r=mid;
		}		
		else{
			l=mid;
		}

}
return mid;

}
int main(){
	int t,ans=0;
	cin>>n>>q;
	for(int i=0;i<n;i  ){
		for(int a=0;a<n;a  ){
			cin>>t;
			g[i][a]=g[a][i]=t;
			g_copy[i][a]=g[a][i]=t; //邻接矩阵存图
		}
	}
	for(int i=0;i<n;i  ){
		for(int a=0;a<n;a  ){
			cin>>t;
			low[i][a]=low[a][i]=t;
			low_copy[i][a]=low_copy[i][a]=t;  //邻接矩阵存图
		}
	}

for(int i=0;i<n;i  ){
	for(int a=0;a<n;a  ){
		for(int b=0;b<n;b  ){
			g_copy[a][b]=min(g_copy[a][b],g_copy[a][i] g_copy[i][b]);  //对一开始的图进行floyd
		}
	}
}
for(int i=0;i<n-1;i  ){
	for(int j=i 1;j<n;j  ){
		ans =g_copy[i][j];  
	}
}			
ans*=2;  //求出P值
if(ans<=q){
	cout<<"0";
	return 0; //直接结束
}

ans=0;  //记得归零
for(int i=0;i<n;i  ){
	for(int a=0;a<n;a  ){
		for(int b=0;b<n;b  ){
			low_copy[a][b]=min(low_copy[a][b],low_copy[a][i] low_copy[i][b]);  //对下限值进行floyd
		}
	}
}
for(int i=0;i<n-1;i  ){
	for(int j=i 1;j<n;j  ){
		ans =low_copy[i][j];
	}
}			
ans*=2;  //求出P值
if(ans>=q){
	cout<<"-1";
	return 0;  //直接结束
}
ans=searchans(-1,maxx); //二分答案求天数
cout<<ans;

return 0;

}

这篇好文章是转载于：学新通技术网