❥小虾目前大三，我校在大一下开设《数据结构》这门课，大二上开了《算法设计与分析》这门课，很庆幸这两门课的上机考试总成绩一门100，一门99，最后总分也都90+。下文会给出机试的33道题目＆AC代码＆注释供大家参考。
❥《算法设计与分析》用的是屈婉玲老师的教材，上机习题用的是王晓东前辈的，开授这门课的教授表示：考虑到算法具有一定的难度，并不适合所有的学生，只讲授和考察四个专题的内容（贪心、递归与分治、动态规划、回溯与分值限界）
❥课程考核主要分为平时练习、多次机试和最后的笔试（卷面考试），笔试大概主要是考察结合问题情景设计算法，写出伪代码并进行相应的分析。每个专题限时开放若干道机试练习题，不给出答案，后面的机试就是给出里面的题目进行考核，按测试点给分（会有少部分测试点改成大数或特例）。
❥废话不多说，下面将四大专题的 习题&答案 分享给大家，希望能提供力所能及的帮助，原创不易，感谢支持！
之前按照专题分类发布过，这次作为一个合集发布，于人于己提供方便~ 对应的专题链接也会放在文末。
❥转载随意，但请注明出处！
☀️【专题】贪心
⭐️外币兑换问题
❀题面：
外币兑换是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定 1 美元可以买 0.7 英镑，1 英镑可以买 9.5 法郎，且 1 法郎可以买到 0.16 美元。通过货币兑换，一个商人可以从 1 美元开始买入，得到 0.7×9.5×0.16=1.064 美元，从而获得 6.4%的利润。
算法设计：给定 n 种货币c1,c2,...,cn的有关兑换率，试设计一个有效算法，用以确定是否存在有收益的兑换可能。
【输入形式】
输入数据：输入数据含有多个测试数据项：每个测试数据的第一行中只有1个整数n(1<=n<=30)，表示货币总种类数。其后n行给出n种货币的名称。接下来的一行中有1个整数m，表示有m种不同的货币兑换率。其后m行给出m种不同的货币兑换率，每行有3个数据项ci，rij和cj，表示货币ci和cj的兑换率为rij。每个测试数据项以空行分隔(测试数据以0结束)。
【输出形式】
对每个测试数据项，如果存在套汇的可能性则输出“Case j Yes”， 否则输出“Case j No”。(注意大小写)
【样例输入】
3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar
0
【样例输出】
case 1 Yes
case 2 No
❀代码&注释：
/*
--------------------------------------
--------Problem: 8936.外币兑换问题----
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MAXN 520
using namespace std;
int n;
double Map[MAXN][MAXN];
void InitMap() ///初始化地图
{
for(int i=1; i<=n; i++)
{
Map[i][i] = 1; ///自身兑换自身的汇率为1
for(int j=i+1; j <= n; j++)
Map[i][j] = Map[j][i] = 0; ///0代表两种货币不能兑换
}
}
void Flody() ///借助Flody求解最短路径的思路求解问题
{
for(int k=1; k<=n; k++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(Map[i][k]*Map[k][j]>Map[i][j]) ///如果货币i兑换成k再兑换成j，比i直接兑换成j所得j货币更多，更新
Map[i][j] = Map[i][k]*Map[k][j];
}
}
}
}
int main()
{
int t=0;
while(~scanf("%d",&n))
{
if(n==0) break;
InitMap();
int num;
char name[50],str1[50],str2[50];
double temp;
map<string,int>m; ///用map来处理货币对应的下标
for(int i=1; i<=n; i++)
{
scanf("%s",name);
m[name] = i;
}
scanf("%d",&num);
for(int i=0; i<num; i++)
{
scanf("%s%lf%s",str1,&temp,str2);
int t1 = m[str1];
int t2 = m[str2];
Map[t1][t2] = temp; ///代表t1可以兑换成temp个t2.
}
Flody();
int flag = 1;
for(int i=1; i<=n; i++)
{
if(Map[i][i]>1) ///如果第i种货币经过来回兑换后，比原来钱多了，则就可以通过这样的方式赚到钱
{
printf("Case %d Yes\n",++t);
flag = 0;
break;
}
}
if(flag) ///代表无论如何兑换，都会赔本，则输出No.
printf("Case %d No\n",++t);
}
return 0;
}⭐️磁盘文件最优存储问题
❀题面：
【输出形式】
将计算出的最小期望检索时间输出。
【样例输入】
5
33 55 22 11 9
【样例输出】
0.547396
❀代码&注释：
/*
--------------------------------------
------Problem: 磁盘文件最优存储问题---
------------------Author--------------
------------------XZITXX--------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool cmp(int a,int b){return a>b;}
/*将数组a的值排序使其元素的分布从中间往两边依次减少*/
void strageSort(int n,int a[])
{
int i,k,mid;
sort(a,a+n,cmp);
mid = n/2;
int b[n+1];
b[mid] = a[0];
for(i=1,k=1; i<n; i++,k++) {//数组a的值分布从中间往两边依次减少
b[mid-k] = a[i];
i++;
if(i!=n) b[mid+k] = a[i];
}
for(int i=0; i<n; i++) a[i] = b[i];//经变化后的a数组
}
void minStorage(int n,int a[])
{
int sum = 0;
for(int i=0; i<n; i++) sum += a[i];
double result = 0;
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++) //从磁道0-n-1。计算它们的磁道间的检索时间
result += (a[i]*1.0/sum)*(a[j]*1.0/sum)*(j-i);
cout<< result<<endl;
}
int main()
{
int n,k,mid,i;
cin>>n;
int a[n+1];
for(int i=0; i<n; i++) cin>>a[i];
strageSort(n,a);
minStorage(n,a);
return 0;
}⭐️会场安排问题
❀题面：
假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的算法进行安排，求出最少需要的会场数。
算法设计：对于给定的 k 个待安排的活动，计算使用最少会场的时间表。
【输入形式】
输入数据:第一行有 1 个正整数 k，表示有 k 个待安排的活动。接下来的 k 行中，每行有 2 个正整数，分别表示 k 个待安排的活动开始时间和结束时间。时间以 0 点开始的分钟计。
【输出形式】
将计算出的最少会场数输出。【样例输入】
5
1 23
12 28
25 35
27 80
36 50
【样例输出】
3
❀代码&注释：
/*
--------------------------------------
------------Problem: 会场安排问题-----
------------------Author--------------
------------------XZITXX--------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
typedef struct {int s,f;} Act;
bool cmp(const Act & a, const Act & b){
return a.s<b.s ;
}
int main()
{
bool cmp(const Act & a, const Act & b);
int n,i,j,max;
while(scanf("%d",&n)!=EOF)
{
Act a;
vector<Act>v;
int count,k;
for(i=0; i<n; i++)
{
scanf("%d %d",&a.s,&a.f);
v.push_back(a);
}
sort(v.begin(),v.end(),cmp);
max=0;
for(i=0; i<v.size(); i++)
{
count=1;
for(j=i-1; j>=0; j--)
if(v[i].s<v[j].f) count++;
if(count>max) max=count;
}
printf("%d\n",max);
}
return 0;
}⭐️非单位时间任务安排问题
❀题面：
【样例输入】
7
1 4 70
2 2 60
1 4 50
1 3 40
1 1 30
1 4 20
3 6 80
【样例输出】
110
❀代码&注释：
/*
--------------------------------------
-----Problem: 非单位时间任务安排问题--
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;//任务个数
struct task{
int t;//任务时间
int d;//截止时间
int w;//惩罚时间
};
task a[100];
int bestw;//存储最短的任务惩罚时间
int w;//当前的任务惩罚时间
int t;//当前所做任务总时间
int x[100];
void backtrack(int i)
{
if(i>n)//到达叶节点
{bestw=w;return;}
/*约束条件：所做任务总时间是否<=当前任务截止时间，成立进入左子树*/
if(t+a[i].t<=a[i].d)
{
t+=a[i].t;//更新总时间
backtrack(i+1);
t-=a[i].t;//回溯结束时时间要还原
}
/*限界函数：当前总惩罚是否<=bestw，成立进入右子树，否则剪枝*/
if(w+a[i].w<=bestw)
{
w=w+a[i].w;
backtrack(i+1);
w=w-a[i].w;
}
}
int main()
{
cin>>n;//输入任务个数
w=0;t=0;bestw=1000;//先将bestw设置为一个较大的值
for(int i=1; i<=n; ++i)
cin>>a[i].t>>a[i].d>>a[i].w;
backtrack(1);
cout<<bestw<<endl;
return 0;
}⭐️硬币找钱问题
❀题面：
不小心丢了...
❀代码&注释：
/*
--------------------------------------
----------Problem: 硬币找钱问题-------
------------------Author--------------
------------------XZITXX--------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 20000 ;
int change[N]; // change[i]为面值为i的钱至少需要的硬币个数
int dp[N]; // dp[i]为当前拥有的硬币数量条件下表示面值为i的最少硬币个数
int value[6] = {1,2,4,10,20,40}; // 每种硬币对应面值，依次为1，2,4,10,20,40个五分，即5,10,20,50,100,200；
int number[6]; // 对应于当前拥有的每种硬币个数
void init() // 计算change[i]
{
int i,j;
for(i=0; i<N; i++) change[i] = -1;
change[0] = 0;
for(i=0; i<6; i++)
{
for(j=value[i]; j<N; j++) // 这里使用完全背包，不能理解的话可参考背包九讲
{
if(change[j-value[i]]!=-1)
{
int temp = change[j-value[i]]+1;
if(change[j]==-1 || temp<change[j]) change[j] = temp;
}
}
}
}
int main()
{
init(); //计算出change[i]
while (scanf(" %d%d%d%d%d%d " , &number[0], &number[1], &number[2], &number[3], &number[4], &number[5]) != EOF)
{
int i,j,kk,sum=0;
for(kk=0; kk<6; kk++) sum += number[kk];
if(sum==0 ) break;
double weight;
scanf("%lf" ,&weight);
weight = weight*100 ;
int w = int(weight+0.0000001); //处理精度问题
if(w%5!=0) // 若不能整除，则无法表示
{
printf("impossible\n");
continue ;
}
else w = w/5;
memset(dp,-1,sizeof(dp));
dp[0] = 0;
int bigger = 0;
for(i=0; i<6; i++) //计算顾客支付面值i需要的最少硬币数dp[i]
{
while(number[i]--) //将混合背包拆成01背包做，写水了点。。。
{
bigger = bigger+value[i];
for(j=bigger; j>=value[i]; j--)
{
if(dp[j-value[i]]!=-1)
{
int temp = dp[j-value[i]]+1;
if(dp[j]==-1 || temp<dp[j]) dp[j] = temp;
}
}
}
}
int ans = -1;
for(i=w; i<=bigger; i++) //寻找最少硬币组合
{
if(dp[i]!=-1)
{
int need = i-w;
if(change[need]!=-1)
{
int temp = dp[i]+change[need];
if(ans==-1 || ans>temp) ans = temp;
}
}
}
if(ans!=-1) printf("%d\n",ans);
else printf("impossible\n");
}
return 0;
}⭐️汽车加油问题
❀题面：
❀代码&注释：
/*
--------------------------------------
---------Problem: 汽车加油问题--------
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
void greedy(int d[],int n,int k) {//汽车加满油之后可以行驶n千米，沿途有k个加油站
int num = 0;
for(int i = 0;i <= k;i++) {
if(d[i] > n) {//加油站之间的距离
cout<<"no solution\n"<<endl;
break;
}
}
for(int i = 0,sum = 0;i <= k;i++) {
sum += d[i];//加油站间距离相加
if(sum > n) {//车无法达到第i个加油站,加油一次，s等于从加过油的地方开始计
num++;
sum = d[i];
}
}
cout<<num<<endl;
}
int main()
{
int i,n,k;
int d[1000];
cin>>n>>k;
for(i=0; i<=k; i++) cin>>d[i];
greedy(d,n,k);
}☀️【专题】递归与分治
⭐️双色Hanoi塔问题
❀题面：
设A、B、C 是3 个塔座。开始时，在塔座A 上有一叠共n 个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1，2，……，n，奇数号圆盘着红色，偶数号圆盘着蓝色，如图所示。现要求将塔座A 上的这一叠圆盘移到塔座B 上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：
规则(1)：每次只能移动1 个圆盘；
规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则(3)：任何时刻都不允许将同色圆盘叠在一起；
规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C 中任一塔座上。
试设计一个算法，用最少的移动次数将塔座A 上的n 个圆盘移到塔座B 上，并仍按同样顺序叠置。对于给定的正整数n，计算最优移动方案。
【输入形式】
输入数据：第1 行是给定的正整数n。
【输出形式】
将计算出的最优移动方案输出：文件的每一行由一个正整数k 和2 个字符c1 和c2 组成，表示将第k 个圆盘从塔座c1 移到塔座c2 上。
【样例输入】
3
【样例输出】
1 A B
2 A C
1 B C
3 A B
1 C A
2 C B
1 A B
❀代码&注释：
/*
--------------------------------------
------Problem: 8776.双色Hanoi塔问题---
-------------------Author-------------
-------------------XZITXX-------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
int k=0,n,i;
int f1[1600],f2[1600],f3[1600];
void mov(int n,char a,char c,char b)
{
if(n==0) return;
mov(n-1,a,b,c ); //把（N-1）片从A柱移到B柱，C作为过渡柱
k++;
f1[k]=n;
f2[k]=a;
f3[k]=c;//把A柱上剩下的一片直接移到C柱
mov(n-1,b,c,a ); //把B柱上的（N-1）片从B柱移到C柱，A柱是过渡柱
}
int main()
{
scanf("%d",&n);
char x,y;
mov(n,'A','B','C');
for(i=1;i<=k;i++)
{
x=f2[i];
y=f3[i];
printf("%d %c %c\n",f1[i],x,y);
}
return 0;
}⭐️半数集问题
❀题面：
给定一个自然数n，由n 开始可以依次产生半数集set(n)中的数如下。
(1) n∈set(n)；
(2) 在n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。
注意半数集是多重集。
算法设计：对于给定的自然数n，计算半数集set(n)中的元素个数。
【输入形式】
输入数据：每个数据只有1 行，给出整数n。(0<n<1000)（输入数据有多行）
【输出形式】
结果输出：输出的每一行是半数集set(n)中的元素个数。
【样例输入】
6
【样例输出】
6
❀代码&注释：
/*
--------------------------------------
--------Problem: 8777.半数集问题------
------------------Author--------------
------------------XZITXX--------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[1001];
int comp(int n)
{
int ans=1;
if(a[n]>0)return a[n];
for(int i=1;i<=n/2;i++)
ans+=comp(i);
a[n]=ans;
return ans;
}
int main()
{
int n;
while(cin>>n)
{
memset(a,0,sizeof(a));
a[1]=1;
cout<<comp(n)<<endl;
}
return 0;
}⭐️整数因子分解问题
❀题面：
大于1 的正整数n可以分解为：n=x1 * x2*…*xm。
例如，当n=12 时，共有8 种不同的分解式：
12 = 12；
12 = 6 * 2；
12 = 4 * 3；
12 = 3 * 4；
12 = 3 * 2 * 2；
12 = 2 * 6；
12 = 2 * 3 * 2；
12 = 2 * 2 * 3
算法设计：对于给定的正整数n，计算n共有多少种不同的分解式。
【输入形式】
1 个正整数n (1≤n≤2000000000)。
【输出形式】
将计算出的不同的分解式数输出。
【样例输入】
12
【样例输出】
8
❀代码&注释：
/*
--------------------------------------
-----Problem: 8779.整数因子分解问题---
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int dp[10000],a[10000],k=0;
void ul(int num)
{
for(int i=1; i*i<num; i++)
{
if(num%i == 0)
{
a[k++] = i;
a[k++] = num / i;
}
}
if(i*i==num) a[k++] = i;
}
void solve(int n)//采用了动态规划思想，由于本题数据量大，递归会超时
{
dp[0] = 1;
for(int i=1; i<k; i++)
{
dp[i] = 0;
for(int j=0; j<i; j++)
if(a[i]%a[j]==0)
dp[i] += dp[j];//讲大问题逐步转化成一个个小问题
}
}
int main()
{
int n;
cin >> n;
ul(n);//找n的因子有哪些，并存放到数组a中
sort(a, a+k);//注意这个地方，将a有小到大排列起来
solve(n);
printf("%d\n", dp[k-1]);
return 0;
}⭐️排列的字典序问题
❀题面：
n个元素{1,2,..., n }有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下：
字典序值 0 1 2 3 4 5
排列 123 132 213 231 312 321
算法设计：给定n以及n个元素{1,2,..., n }的一个排列，计算出这个排列的字典序值，以及按字典序排列的下一个排列。
【输入形式】
数据的第1 行是元素个数n。接下来的1 行是n个元素{1,2,, n }的一个排列。
【输出形式】
将计算出的排列的字典序值和按字典序排列的下一个排列输出：输出的第一行是字典序值，第2行是按字典序排列的下一个排列。
【样例输入】
8
2 6 4 5 8 1 7 3
【样例输出】
8227
2 6 4 5 8 3 1 7
❀代码&注释：
/*
--------------------------------------
-----Problem: 8782.排列的字典序问题---
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int n,k,*p,t=0,x[16];
x[0]=1;
for(int i=1; i<15; i++) x[i]=x[i-1]*i;
while(cin >> n)
{
k=0;
p=new int[n+1];
for(int i=0; i<n; i++) cin>>p[i];
for(int i=0; i<n; i++)
{
t=0;
for(int j=i+1; j<n; j++)
if(p[j]<p[i]) t++;
k += t*x[n-i-1];
}
cout<<k<<endl;
next_permutation(p,p+n);
for(int i=0; i<n; i++)
cout<<p[i]<<' ';
cout<<endl;
}
return 0;
}⭐️众数问题
❀题面：
给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。
算法设计：对于给定的由n 个自然数组成的多重集S，计算S的众数及其重数。
【输入形式】
输入数据：第1行多重集S中元素个数n；接下来的n行中，每行有一个自然数。
【输出形式】
输出的第1行给出众数，第2 行是重数。
【样例输入】
6
1
2
2
2
3
5
【样例输出】
2
3
❀代码&注释：
/*
--------------------------------------
-----------Problem: 8783.众数问题-----
--------------------Author------------
--------------------XZITXX------------
--------------------------------------
*/
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int main()
{
int n,x=0;
cin >> n;
vector<int> a(n+3);
int sum=0, num=0;
for(int i=0; i<n; i++)
{
cin >> x;
a[x]++;
if(a[x]>sum)
{
sum = a[x];
num = x;
}
if(a[x]==sum && x<num)
{
sum = a[x];
num = x;
}
}
cout << num << endl;
cout << sum << endl;
return 0;
}⭐️输油管道问题
❀题面：
某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。
算法设计：给定 n 口油井的位置,计算各油井到主管道之间的输油管道最小长度总和。
【输入形式】
输入数据：第1 行是油井数n，1<=n<=10000。接下来n 行是油井的位置，每行2个整数x和y，-10000<=x，y<=10000。
【输出形式】
输出数据的第1 行中的数是油井到主管道之间的输油管道最小长度总和。
【样例输入】
5
1 2
2 2
1 3
3 -2
3 3
【样例输出】
6
❀代码&注释：
/*
--------------------------------------
------Problem: 8785. 输油管道问题-----
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include<bits/stdc++.h>
using namespace std;
struct node {int x,y;} well[200000];
bool cmp(node a,node b){
return a.y<b.y;
}
int main()
{
int t;
scanf("%d",&t);
for(int i=0; i<t; i++)
scanf("%d%d",&well[i].x,&well[i].y);
sort(well,well+t,cmp);//排序
int ans=0,middle;
if(t%2==1)//找到中位数
middle=well[t/2].y;
else
middle=(well[t/2].y+well[t/2-1].y)/2;
for(int i=0; i<t; i++)
ans+=abs(well[i].y-middle);//算出长度之和
printf("%d\n",ans);
return 0;
}⭐️集合划分问题
❀题面：
n个元素的集合{1,2,...., n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2，3，4}可以划分为15 个不同的非空子集如下：
{{1}，{2}，{3}，{4}}，
{{1，2}，{3}，{4}}，
{{1，3}，{2}，{4}}，
{{1，4}，{2}，{3}}，
{{2，3}，{1}，{4}}，
{{2，4}，{1}，{3}}，
{{3，4}，{1}，{2}}，
{{1，2}，{3，4}}，
{{1，3}，{2，4}}，
{{1，4}，{2，3}}，
{{1，2，3}，{4}}，
{{1，2，4}，{3}}，
{{1，3，4}，{2}}，
{{2，3，4}，{1}}，
{{1，2，3，4}}
算法设计：给定正整数 n，计算出n个元素的集合{1,2,..., n }可以划分为多少个不同的非空子集。
【输入形式】
输入数据:第1 行是元素个数n。
【输出形式】
将计算出的不同的非空子集数输出.
【样例输入】
5
【样例输出】
52
❀代码&注释：
/*
--------------------------------------
-------Problem: 8787.集合划分问题-----
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int f(int n,int m)
{
if(m==1||n==m)
return 1;
else
return f(n-1,m-1)+f(n-1,m)*m;
}
int main()
{
int n;
while(scanf("%d",&n)==1 && n>=1)
{
int sum=0;
for(int i=1; i<=n; i++) sum+=f(n,i);
printf("%d\n",sum);
}
return 0;
}⭐️集合划分问题2
❀题面：
n 个元素的集合{1,2,..., n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2，3，4}可以划分为15 个不同的非空子集如下：
{{1}，{2}，{3}，{4}}，
{{1，2}，{3}，{4}}，
{{1，3}，{2}，{4}}，
{{1，4}，{2}，{3}}，
{{2，3}，{1}，{4}}，
{{2，4}，{1}，{3}}，
{{3，4}，{1}，{2}}，
{{1，2}，{3，4}}，
{{1，3}，{2，4}}，
{{1，4}，{2，3}}，
{{1，2，3}，{4}}，
{{1，2，4}，{3}}，
{{1，3，4}，{2}}，
{{2，3，4}，{1}}，
{{1，2，3，4}}
其中，集合{{1，2，3，4}}由1 个子集组成；集合{{1，2}，{3，4}}，{{1，3}，{2，4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2，3，4}，{1}}由2 个子集组成；集合{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}，{2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}}由3 个子集组成；集合{{1}，{2}，{3}，{4}}由4 个子集组成。
算法设计： 给定正整数 n 和 m，计算出 n 个元素的集合{1,2,...., n }可以划分为多少个不同的由m个非空子集组成的集合。
【输入形式】
输入数据:第1 行是元素个数n 和非空子集数m。
【输出形式】
将计算出的不同的由m 个非空子集组成的集合数输出。
【样例输入】
43
【样例输出】
6
❀代码&注释：
/*
--------------------------------------
------Problem: 8788.集合划分问题2-----
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int f(int n,int m)
{
if(m==1||n==m) return 1;
else return f(n-1,m-1)+f(n-1,m)*m;
}
int main()
{
int n,m;
cin>>n>>m;
cout<<f(n,m);
return 0;
}⭐️士兵站队问题
❀题面:
在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择x 和y的值才能使士兵们以最少的总移动步数排成一列。
算法设计：计算使所有士兵排成一行需要的最少移动步数。
【输入形式】
输入数据:第1 行是士兵数n，1<=n<=10000。接下来n 行是士兵的初始位置，每行2 个整数x 和y，-10000<=x，y<=10000。
【输出形式】
将计算结果:输出的第1 行中的数是士兵排成一行需要的最少移动步数。
【样例输入】
5
1 2
2 2
1 3
3 -2
3 3
【样例输出】
8
❀代码&注释：
/*
---------------------------------------
-------Problem: 8789.士兵站队问题------
------------------Author---------------
------------------XZITXX---------------
---------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a,b;
int x[20002],y[20002];
int abss(int a,int b)
{
if(a>b) return a-b;
else return b-a;
}
int main()
{
scanf("%d",&n);
for(int i=0; i<n; ++i)
scanf("%d %d",&x[i],&y[i]);
sort(x,x+n);
sort(y,y+n);
for(int i=0; i<n; ++i) x[i]-=i;
sort(x,x+n);
for(int i=0; i<n; ++i)
{
a += abss(x[n/2],x[i]);
b += abss(y[n/2],y[i]);
}
printf("%d",a+b);
return 0;
}⭐️标准2维表问题
❀题面：
设 n 是一个正整数。2′n 的标准2 维表是由正整数1，2，…，2n 组成的2′n 数组，该数组的每行从左到右递增，每列从上到下递增。2′n的标准2 维表全体记为Tab(n)。例如，当n=3时Tab(3)如下：
算法设计：给定正整数n，计算Tab(n)中2′n的标准2 维表的个数。
【输入形式】
输入数据:第一行有1 个正整数n。
【输出形式】
将计算出的Tab(n)中2′n的标准2 维表的个数输出。
【样例输入】
3
【样例输出】
5
❀代码&注释：
/*
--------------------------------------
------Problem: 8790.标准2维表问题-----
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define CARRYS 10000
int prmStatic(int *prm,int num) // 产生小于num的所有质数。
{
int total=0,i=2,j;
int *judge = new int[num+1];
for(j=1; j<=num; j++) judge[j]=j;
while(i<num+1)
{
while(!judge[i]) i++;
prm[total]=i;
total++;
for(j=i; j<num+1; j+=i) judge[j]=0;
}
return total;
}
void breakNum(int left,int right,int *prm,int *stat) //质因数分解
{
int k,m,n,t;
k=m=right,n=left,t=0;
while(prm[t]<=k)
{
while(left!=right)
{
left/=prm[t];
right/=prm[t];
stat[t] += (right-left);
}
t++;
right=m;
left=n;
}
}
void carryPro(int *poly, int carry, int total, int &curpos)
{
poly[curpos] += carry;
int i = poly[curpos]/CARRYS;
if((curpos<total)||carry)
{
poly[curpos]%= CARRYS;
curpos++;
carryPro(poly, i, total, curpos);
}
}
void mulAll(int&m,int *prm, int *result, int prmsum, int *Last)
//累乘
{
Last[0] = 1,m=1;
for(int i=0; i<prmsum; i++)
{
for(int t=0; t<result[i]; t++)
{
for(int k=0; k<m; k++)
Last[k] *= prm[i];
for(int j=0; j<m; j++)
if(Last[j]>=CARRYS)
{
int k = j+1;
carryPro(Last, Last[j]/CARRYS, m, k);
Last[j] %= CARRYS;
if(m<k+1) m=k+1;
break;
}
}
for(int j=m-1; j>=0; j--)
{
if(Last[j]!=0) break;
m--;
}
}
}
void Print(int polysum, int *last)//输出结果
{
printf("%d",last[polysum-1]);
for(int i=polysum-2; i>=0; i--)
{
for(int j=CARRYS/10; j; j/=10)
printf("%d",last[i]/j%10);
}
}
int main()
{
int m,presum=0;
scanf("%d",&m);
int *prm = new int[m];
int *last = new int[1500];
memset(prm, 0, 4*m);
presum=prmStatic(prm,m*2);
int *mole = new int[presum];
int *denom = new int[presum];
memset(denom, 0, 4*presum);
memset(mole, 0, 4*presum);
breakNum(1, m+1,prm, denom);
breakNum(m, 2*m,prm, mole);
for(int i=0; i<presum; i++)
mole[i] = mole[i]-denom[i];
memset(last,0,6000);
mulAll(m,prm, mole, presum, last);
Print(m ,last);
delete []mole;
delete []prm;
delete []last;
return 0;
}⭐️马的Hamilton周游路线问题
❀题面：
8* 8 的国际象棋棋盘上的一只马，恰好走过除起点外的其它 63 个位置各一次，最后回到起点。这条路线称为一条马的 Hamilton 周游路线。对于给定的 m* n 的国际象棋棋盘，m 和 n 均为大于 5 的偶数，且 |m-n|≤2，试设计一个分治算法找出一条马的 Hamilton周游路线。对于给定的偶数 m，n≥6，且 |m-n|≤2，计算m′n 的国际象棋棋盘一条马的 Hamilton周游路线。
【输入形式】
第一行有2个正整数m和n，表示给定的国际象棋棋盘由m行，每行n个格子组成。
【输出形式】
将计算出的马的Hamilton周游路线用下面的2 种表达方式输出：
第1 种表达方式按照马步的次序给出马的Hamilton 周游路线。马的每一步用所在的方格坐标(x，y)来表示。x表示行的坐标，编号为0，1，…，m-1；y表示列的坐标，编号为0，1，…，n-1。起始方格为（0，0）。
第2 种表达方式在棋盘的方格中标明马到达该方格的步数。（0，0）方格为起跳步，并标明为第1步。
【样例输入】
6 6
【样例输出】
(0,0) (2,1) (4,0) (5,2) (4,4) (2,3)
(0,4) (2,5) (1,3) (0,5) (2,4) (4,5)
(5,3) (3,2) (5,1) (3,0) (1,1) (0,3)
(1,5) (3,4) (5,5) (4,3) (3,1) (5,0)
(4,2) (5,4) (3,5) (1,4) (0,2) (1,0)
(2,2) (0,1) (2,0) (4,1) (3,3) (1,2)
1 32 29 18 7 10
30 17 36 9 28 19
33 2 31 6 11 8
16 23 14 35 20 27
3 34 25 22 5 12
24 15 4 13 26 21
实现的有点误差，下面是代码对应的输出：
1 30 33 16 3 24
32 17 2 23 34 15
29 36 31 14 25 4
18 9 6 35 22 13
7 28 11 20 5 26
10 19 8 27 12 21
❀代码&注释：
/*
-------------------------------------------
---Problem: 8781.马的Hamilton周游路线问题---
-------------------Author------------------
-------------------XZITXX------------------
-------------------------------------------
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5+10;
struct node {int to,next;} edge[2*maxn];
int head[maxn],cnt,vis[maxn],deep[maxn],num[maxn],m,n;
void add(int u, int v)
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
queue<int>q;
void bfs()
{
while(!q.empty())
{
int x = q.front(); q.pop();
for(int i=head[x]; i>=0; i=edge[i].next)
{
int to = edge[i].to;
if(deep[to]==0 || deep[to] == deep[x]+1) {
num[to] += num[x];
deep[to] = deep[x]+1;
if(num[to] == m) {
cout<<"YES"<<endl<<to<<endl;
exit(0);
}
if(!vis[to]) q.push(to);
vis[to] = 1;
}
}
}
}
int main()
{
int i,j,a,b,cnt=0;
scanf("%d %d",&n,&m);
memset(head,-1,sizeof(head));
for(i=0; i<n-1; i++) {
scanf("%d %d",&a,&b);
add(a,b); add(b,a);
}
for(i=0; i<m; i++) {
scanf("%d",&a); q.push(a);
deep[a]=1; vis[a]=1; num[a]=1;
}
if(m==1) {cout<<"YES"<<endl<<a<<endl; return 0;}
bfs();
cout<<"NO"<<endl;
return 0;
}☀️【专题】动态规划
⭐️最小 m 段和问题
❀题面：
给定 n 个整数组成的序列，现在要求将序列分割为 m 段，每段子序列中的数在原序列
中连续排列。如何分割才能使这 m段子序列的和的最大值达到最小？
算法设计：给定 n 个整数组成的序列,计算该序列的最优 m 段分割，使 m 段子序列的和的最大值达到最小
【输入形式】
输入数据：第 1 行中有 2 个正整数 n 和 m。正整数 n 是序列的长度；正整数 m是分割的段数。接下来的一行中有 n 个整数。
【输出形式】
将计算结果输出：第 1 行中的数是计算出的 m段子序列的和的最大值的最小值。
【样例输入】
1 1
10
【样例输出】
10
❀代码&注释：
/*
--------------------------------------
------Problem: 8918.最小m段和问题-----
-----------------Author--------------
-----------------XZITXX--------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int n,m,a[1005];
int dp[1005][1005];
int sum[1005][1005];
int main()
{
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
dp[i][j] = 1000000000;
for(int i=1; i<=n; i++) {
int num = 0;
for(int j=i; j<=n; j++) {
num += a[j];
sum[i][j] = num;
}
dp[i][1] = sum[1][i];
}
for(int i=2; i<=n; i++) {
for(int j=2; j<=i && j<=m; j++) {
int p;
for(int k=1; k<i; k++)
dp[i][j] = min(dp[i][j], max(dp[k][j - 1], sum[k + 1][i]));
}
}
cout << dp[n][m] << endl;
return 0;
}⭐️最大 k 乘积问题
❀题面：
设 I 是一个 n 位十进制整数。如果将 I 划分为 k 段，则可得到 k 个整数。这 k 个整数的
乘积称为 I 的一个 k 乘积。试设计一个算法，对于给定的 I 和 k，求出 I 的最大 k 乘积。
算法设计：对于给定的 I 和 k，计算 I 的最大 k 乘积。
【输入形式】
输入数据：第 1 行中有 2 个正整数 n 和 k。正整数 n 是序列
的长度；正整数 k 是分割的段数。
接下来的一行中是一个 n 位十进制整数。（n<=10）
【输出形式】
将计算结果输出：第 1 行中的数是计算出的最大 k 乘积。
【样例输入】
2 1
15
【样例输出】
15
❀代码&注释：
/*
--------------------------------------
-----Problem: 8917.最大k乘积问题------
----------------Author---------------
----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
int dp[15][15]; //最大乘积数组
char numstr[15];
int num[15];
int getValue(int i,int j) {
int sum = 0;
for(int k=i; k<j; k++) {
sum += num[k];
sum *= 10;
}
return sum + num[j];
}
void dpAlgo(int l,int k) {
for(int i=1; i<=l; i++)
dp[i][1] = getValue(1,i);
for(int i=0; i<=l; i++) {
for(int j=2; j<=k; j++) {
int temp = 0;
for(int d=1; d<i; d++)
temp = max(temp,dp[d][j-1] * getValue(d+1,i));
dp[i][j] = temp;
}
}
}
int main()
{
int l,k;
cin>>l>>k>>numstr;
for(int i=0; i<l; i++)
num[i+1] = numstr[i] - '0';
dpAlgo(l,k);
cout << dp[l][k];
return 0;
}⭐️最大长方体问题
❀题面：
一个长，宽，高分别为 m,n,p 的长方体被分割成个 m*n*p 个小立方体。每个小立方体内有一个整数。试设计一个算法，计算出所给长方体的最大子长方体。子长方体的大小由它所含所有整数之和确定。
算法设计：对于给定的长，宽，高分别为 m,n,p 的长方体，计算最大子长方体的大小
【输入形式】
输入数据：第 1 行是 3 个正整数 m,n,p，1≤m,n,p≤50。接下来 m*n 行每行 p 个正整数，表示小立方体中的数。
【输出形式】
将计算结果输出：第 1 行中的数是计算出的最大子长方体的大小。
【样例输入】
3 3 3
0 -1 2
1 2 2
1 1 -2
-2 -1 -1
-3 3 -2
-2 -3 1
-2 3 3
0 1 3
2 1 -3
【样例输出】
14
❀代码&注释：
/*
--------------------------------------
-----Problem: 8916.最大长方体问题-----
---------------Author-----------------
---------------XZITXX-----------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
int maxsum(int n,int *a)
{
int sum=0,b=0;
for (int i=1; i<=n; i++)
{
if(b>0) b+=a[i];
else b=a[i];
if(b>sum) sum=b;//记录最大值
}
return sum;
}
int maxsum2(int m,int n, int **a){
int sum=0;
int *b=new int [n+1];
for (int i=1; i<=m; i++) {
for(int k=1; k<=n; k++)
b[k]=0;//置0
for(int j=i; j<=m; j++) {//动规思想，将m分成1~i和i+1~m两段
for (int k=1; k<=n; k++)
b[k] += a[j][k];
int max=maxsum(n,b);
if(max>sum) sum=max;
}
}
return sum;
}
int maxsum3(int m,int n,int p,int ***a)
{
int sum=0;
int **c=new int*[n+1];
for(int i=1; i<=n; i++) c[i]=new int [p+1];
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
for(int k=1; k<=p ; k++) c[j][k]=0;//置0
for (int l=i; l<=m; l++) {//和二维的思想一样
for(int j=1; j<=n; j++)
for(int k=1; k<=p ; k++) c[j][k]+=a[l][j][k];
int max=maxsum2(n,p,c);
if(max>sum) sum=max;
}
}
return sum;
}
int main()
{
int m,n,p,***a;
cin>>m>>n>>p;
a=new int**[m+1];
for(int i=1; i<=m; i++) a[i]=new int*[n+1]; //一维
for(int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
a[i][j]=new int[p+1]; //二维
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
for(int k=1; k<=p; k++)
cin>>a[i][j][k]; //三维
cout<<maxsum3(m,n,p,a);
}⭐️最少硬币问题
❀题面：
设有 n 种不同面值的硬币，各硬币的面值存于数组 T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组 Coins[1:n]中。对任意钱数 0≤m≤20001，设计一个用最少硬币找钱 m 的方法。
算法设计：对于给定的 1≤n≤10，硬币面值数组 T 和可以使用的各种面值的硬币个数数组 Coins，以及钱数 m，0≤m≤20001，计算找钱 m的最少硬币数
【输入形式】
输入数据：第一行中只有 1 个整数给出n 的值,第 2 行起每
行 2 个数，分别是 T[j]和 Coins[j]。最后 1 行是要找的钱数 m。
【输出形式】
将计算出的最少硬币数输出。问题无解时输出-1。
【样例输入】
3
1 3
2 3
5 3
18
【样例输出】
5
❀代码&注释：
/*
--------------------------------------
------Problem: 8913.最少硬币问题------
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
/*多重背包(硬币种类有限制，硬币数目有限制)*/
#include <iostream>
using namespace std;
const int maxvalue = 20001;
const int coinnum = 15;
int mymin(int a,int b){
return a < b ? a : b;
}
int main()
{
int n;
cin >> n;
int coin[coinnum];
int coincount[coinnum];
for(int i=0; i<n; i++)
{
cin >> coin[i];
cin >> coincount[i];
}
int m;
cin >> m;
//钱数为dp[i]是的硬币数目
int *dp = new int[maxvalue]();
//重点错误
//for(int i=0; i<=m; i++)是错的
for(int i=1; i<=m; i++) dp[i] = maxvalue;
int i,j,k;
for(i=0; i<n; i++)//硬币面值的种数
{
for(j=1; j<=coincount[i]; j++)//硬币的面值的个数
{
for(k=m; k>=coin[i]; k--) //动态迁移方程为
dp[k] = mymin(dp[k - coin[i]] + 1, dp[k]);
}
}
if(dp[m] == maxvalue)
cout << -1 << endl;
else cout << dp[m] << endl;
return 0;
}⭐️石子合并问题
❀题面：
在一个圆形操场的四周摆放着 n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将 n 堆石子合并成一堆的最小得分和最大得分。
算法设计：对于给定 n 堆石子,计算合并成一堆的最小得分和最大得分
【输入形式】
输入数据：第 1 行是正整数 n，1≤n≤100，表示有 n 堆石子。
第二行有 n 个数，分别表示每堆石子的个数。
【输出形式】
将计算结果输出：第 1 行中的数是最小得分；第 2 行中的数是最大得分。
【样例输入】
4
4 4 5 9
【样例输出】
43
54
❀代码&注释：
/*
--------------------------------------
------Problem: 8920.石子合并问题------
---------------Author----------------
---------------XZITXX----------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
const int INF=0x7fffffff;
int n,m,ans1,ans2;
int A[205],f1[205][205],f2[205][205];
int dfs1(int L,int R){ //求出最小得分
if(f1[L][R])return f1[L][R]; //已保存的状态不必搜索
if(L==R) return f1[L][R]=0; //L==R时返回0
int res=INF; //初始值赋为最大值以求最小值
for(int k=L;k<R;k++) //枚举K搜索
res=min(res,dfs1(L,k)+dfs1(k+1,R)+A[R]-A[L-1]);
return f1[L][R]=res; //记录状态
}
int dfs2(int L,int R){ //求出最大得分
if(f2[L][R])return f2[L][R];
if(L==R) return f2[L][R]=0; //若初始值为0可省略该句
int res=0; //初始值设为0
for(int k=L;k<R;k++)
res=max(res,dfs2(L,k)+dfs2(k+1,R)+A[R]-A[L-1]);
return f2[L][R]=res;
}
int main(){
std::ios::sync_with_stdio(false);//取消cin与stdin同步,加速读入
cin>>n;
for(int i=1;i<=n;i++){
cin>>A[i];
A[i+n]=A[i]; //因为是环所以保存为长度为2n的链以保证不会漏解
}
for(int i=1;i<=2*n;i++) //求出前缀和
A[i]+=A[i-1];
dfs1(1,2*n);dfs2(1,2*n); //搜索出1-2n的最大得分与最小得分
ans1=INF; ans2=0;
for(int i=1;i<=n;i++){
ans1=min(f1[i][n+i-1],ans1);//选出答案
ans2=max(f2[i][n+i-1],ans2);
}
cout<<ans1<<"\n"<<ans2;
return 0;
}⭐️序关系计数问题
❀题面：
用关系“<”和“=”将 3 个数 A、B 和 C 依序排列时有 13 种不同的序关系：A=B=C，A=B<C，A<B=C，A<B<C，A<C<B，A=C<B，B<A=C，B<A<C，B<C<A，B=C<A，C<A=B，C<A<B，C<B<A。将n 个数（1 ≤ n ≤50）依序排列时有多少种序关系。
算法设计：计算出将 n 个数（1 ≤ n ≤50）依序排列时有多少种序关系
【输入形式】
输入数据：输入数据有多行，每行提供一个数n 。
【输出形式】
将找到的序关系数输出：一行一个。
【样例输入】
3
5
【样例输出】
13
541
❀代码&注释：
/*
--------------------------------------
-----Problem: 8923.序关系计数问题-----
---------------Author-----------------
---------------XZITXX----------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define MAX_N 51
using namespace std;
__int64 dp[MAX_N][MAX_N]; //dp[i][j]：i个数，有j个‘<’链接，共有多少种情况
int main()
{
int n,i,j;
for(i=0; i<MAX_N; i++) dp[i][0]=1;
for(i=0; i<MAX_N; i++)
for(j=1; j<i; j++)
dp[i][j] = (j+1)*(dp[i-1][j]+dp[i-1][j-1]);
for(i=0; i<MAX_N; i++)
for(j=0; j<i; j++)
dp[i][i] += dp[i][j]; //dp[i][i]存放每一行的和
while(scanf("%d",&n)==1){
printf("%I64d\n",dp[n][n]);
}
return 0;
}⭐️汽车加油行驶问题
❀题面：
给定一个N*N 的方形网格，设其左上角为起点，坐标为（1,1），X 轴向右为正，Y 轴向下为正，每个方格边长为1。一辆汽车从起点出发驶向右下角终点，其坐标为（N,N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守
如下规则：（1）汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。（2）当汽车行驶经过一条网格边时，若其 X 坐标或 Y 坐标减小，则应付费用B，否则免付费用。（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。（4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。（5）(1)～(4)中的各数N、K、A、B、C均为正整数。
算法设计：求汽车从起点出发到达终点的一条所付费用最少的行驶路线
【输入形式】
输入数据：
第一行是N，K，A，B，C的值，2 ≤ N ≤ 100，2 ≤ K ≤ 10。第二行起是一个N*N 的0-1方阵，每行N 个值，至N+1行结束。方阵的第i行第j 列处的值为1 表示在网格交叉点（i，j）处设置了一个油库，为0 时表示未设油库。各行相邻的2 个数以空格分隔。
【输出形式】
将找到的最优行驶路线所需的费用，即最小费用输出：第1行中的数是最小费用值。
【样例输入】
9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0
【样例输出】
12
❀代码&注释：
/*
--------------------------------------
----Problem: 8910.汽车加油行驶问题----
----------------Author---------------
----------------XZITXX---------------
--------------------------------------
*/
#include<bits/stdc++.h>
#include<set>
#include<map>
using namespace std;
#define MAX 120
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Line
{
int v,next,w;
}e[MAX*MAX*MAX];
int h[MAX*MAX],cnt=1,tot;
int m[MAX*MAX],g[MAX][MAX],n,K,A,B,C;
bool vis[MAX*MAX][15];
inline void Add(int u,int v,int w)
{
e[cnt]=(Line){v,h[u],w};h[u]=cnt++;
}
int dis[MAX*MAX][15];
void SPFA()
{
memset(dis,63,sizeof(dis));
dis[g[1][1]][K]=0;
queue<int> Q,Q1;
Q.push(g[1][1]);Q1.push(K);
while(!Q.empty())
{
int u=Q.front(),t=Q1.front();
Q.pop();Q1.pop();
if(t!=0)
{
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v,gg=t-1,Dis=dis[u][t]+e[i].w;
if(m[v])gg=K,Dis+=A;
if(dis[v][gg]>Dis)
{
dis[v][gg]=Dis;
if(!vis[v][gg])vis[v][gg]=true,Q.push(v),Q1.push(gg);
}
}
}
int v=u,gg=K,Dis=dis[u][t]+C+A;
if(dis[v][gg]>Dis)
{
dis[v][gg]=Dis;
if(!vis[v][gg])vis[v][gg]=true,Q.push(v),Q1.push(gg);
}
vis[u][t]=false;
}
}
int main()
{
n=read();K=read();A=read();B=read();C=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
g[i][j]=++tot,m[g[i][j]]=read();;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
if(i!=n) Add(g[i][j],g[i+1][j],0);
if(j!=n) Add(g[i][j],g[i][j+1],0);
if(i!=1) Add(g[i][j],g[i-1][j],B);
if(j!=1) Add(g[i][j],g[i][j-1],B);
}
SPFA();
int ans=1e9;
for(int i=0;i<=K;++i)ans=min(ans,dis[g[n][n]][i]);
printf("%d\n",ans);
return 0;
}⭐️租用游艇问题
❀题面：
长江游艇俱乐部在长江上设置了 n 个游艇出租站 1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j),1≤i<j≤n。试设计一个算法，计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。
算法设计：对于给定的游艇出租站 i 到游艇出租站 j 之间的租金为 r(i,j),1≤i<j≤n，计算从游艇出租站 1 到游艇出租站 n 所需的最少租金
【输入形式】
输入数据：第 1 行中有 1 个正整数 n（n<=200），表示有 n个游艇出租站。接下来的 n-1 行是 r(i,j),1≤i<j≤n。
【输出形式】
将计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金输出。
【样例输入】
3
5 15
7
【样例输出】
12
❀代码&注释：
/*
--------------------------------------
------Problem: 8924.租用游艇问题------
-----------------Author--------------
-----------------XZITXX--------------
--------------------------------------
*/
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int n,v[222][222];
int dp[222];//dp[i]表示到第i个游艇出租站所需的最少租金
int main()
{
scanf("%d",&n);
for(int i=1; i<n; i++)
for(int j=i+1; j<=n; j++)
scanf("%d",&v[i][j]);
memset(dp,INF,sizeof(dp));
dp[1]=0;
for(int i=2; i<=n; i++)
for(int j=1; j<i; j++)
dp[i] = min(dp[i],dp[j]+v[j][i]);
printf("%d\n",dp[n]);
return 0;
}⭐️红黑树的红色内结点问题
❀题面：
红黑树是一类特殊的二叉搜索树，其中每个结点被“染成”红色或黑色。若将二叉搜索树结点中的空指针看作是指向一个空结点，则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为-1。
一棵红黑树是满足下面“红黑性质”染色二叉搜索树：
(1)每个结点被染成红色或黑色；
(2)每个前端结点为黑色结点；
(3)任一红结点的儿子结点均为黑结点；
(4)在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。
从红黑树中任一结点 x 出发(不包括结点 x)，到达一个前端结点的任意一条路径上的黑结点个数称为结点 x 的黑高度，记作 bh(x)。红黑树的黑高度定义为其根结点的黑高度。图示的二叉搜索树是一棵红黑树。标在结点旁边的数字是相应结点的黑高度。
算法设计：给定正整数 n，试设计一个算法，计算出在所有含有 n 个结点的红黑树中，红色内结点个数的最小值和最大值
【输入形式】
输入数据：第一行是正整数 n，1<n<5000。
【输出形式】
将红色内结点个数的最小值和最大值输出：第 1 行是最小值，第 2行是最大值。
【样例输入】
8
【样例输出】
1
4
❀代码&注释：
/*
--------------------------------------
-----8830. 红黑树的红色内结点问题-----
------------------Author-------------
------------------XZITXX--------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
int main()
{
scanf("%d",&n);
m=n+1;
while(m>1) {
ans+=m&1;m>>=1;
}
printf("%d\n",ans);
m=n+1;ans=0;
while(m>1)
{
if(m==2) ans++;
if((m&3)==1) ans+=m/4*2-1,m/=4,m++;
else if((m&3)==2) ans+=m/4*2,m/=4,m++;
else if((m&3)==3) ans+=m/4*2+1,m/=4,m++;
else ans+=m/4*2,m/=4;
}
printf("%d\n",ans);
return 0;
}⭐️编辑距离问题
❀题面：
设 A 和 B 是 2 个字符串。要用最少的字符操作将字符串 A 转换为字符串 B。这里所说的字符操作包括
(1)删除一个字符；
(2)插入一个字符；
(3)将一个字符改为另一个字符。
将字符串 A 变换为字符串 B 所用的最少字符操作数称为字符串 A 到 B 的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的2个字符串A和B，计算出它们的编辑距离d(A,B)。
算法设计：对于给定的字符串 A 和字符串 B，计算其编辑距离 d(A,B)
【输入形式】
输入数据：第一行是字符串 A，文件的第二行是字符串 B。
【输出形式】
将编辑距离 d(A,B)输出到第 1 行中。
【样例输入】
fxpimu
xwrs
【样例输出】
5
❀代码&注释：
/*
--------------------------------------
------------8829. 编辑距离问题--------
------------------Author--------------
------------------XZITXX--------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
int d[2005][2005];
/*
输入的两个字符数组为a[], b[]，从下标为0开始初始化
长度分别为length_a, length_b
数组d[m][n]存放从a[1:m] 变为 b[1:n]所需要的最少操作
递归公式：
d[i][j] = 0, i=0或j=0 时(即数组的第一行和第一列均为0)
1<=i<=length_a， 1<=j<=length_b
d[i][j] = d[i-1][j-1], a[i-1] == b[j-1]
d[i][j] = min(d[i-1][j-1]+1, d[i][j-1]+1, d[i-1][j]+1), a[i-1] != b[j-1]
最优值：d[length_a][length_b]
*/
int min(int a, int b, int c)
{
int temp = a;
if(temp>b) temp = b;
if(temp>c) temp =c;
return temp;
}
int edit(char *a, char *b)
{
int length_a = strlen(a);
int length_b = strlen(b);
for(int i=0; i<=length_a; i++) d[i][0] = i;
for(int i=0; i<=length_b; i++) d[0][i] = i;
for(int i=1; i<=length_a; i++) {
for(int j=1; j<=length_b; j++) {
if(a[i-1] == b[j-1])
d[i][j] = min(d[i-1][j-1], d[i][j-1]+1, d[i-1][j]+1);
else
d[i][j] = min(d[i-1][j-1]+1, d[i][j-1]+1, d[i-1][j]+1);
}
}
return d[length_a][length_b];
}
int main()
{
char a[2000], b[2000];
cin>>a>>b;
cout<<edit(a,b);
} ⭐️双调旅行售货员问题
❀题面：
欧氏旅行售货员问题是对给定的平面上n 个点确定一条连接这n 个点的长度最短的哈密顿回路。由于欧氏距离满足三角不等式，所以欧氏旅行售货员问题是一个特殊的具有三角不等式性质的旅行售货员问题。它仍是一个NP完全问题。最短双调TSP回路是欧氏旅行售货员问题的特殊情况。平面上n 个点的双调TSP 回路是从最左点开始，严格地由左至右直到最右点，然后严格地由右至左直至最左点，且连接每一个点恰好一次的一条闭合回路。
算法设计：给定平面上 n 个点，计算这 n 个点的最短双调TSP回路
【输入形式】
输入数据：第1 行有1 个正整数n，表示给定的平面上的点数。接下来的n行中，每行2 个实数，分别表示点的x坐标和y坐标。
【输出形式】
将计算的最短双调TSP回路的长度（保留2 位小数）输出。
【样例输入】
7
0 6
1 0
2 3
5 4
6 1
7 5
8 2
【样例输出】
25.58
❀代码&注释：
/*
--------------------------------------
---Problem: 8908.双调旅行售货员问题---
-----------------Author--------------
-----------------XZITXX--------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define db double
using namespace std;
db length(db x1,db y1,db x2,db y2){
db a=(x1-x2)*(x1-x2);
db b=(y1-y2)*(y1-y2);
return sqrt(a+b);
}
int main()
{
int n;
cin>>n;
db x[n+1],y[n+1];
db p[n][n],d[n][n];//p[i][j]表示第i个点与第j个点的距离
for(int i=1; i<=n; i++)//d[i][j](i>j)表示从第i个点到第一个点再到第j个点距离
cin>>x[i]>>y[i];
for(int i=1; i<=n; i++) {//按x坐标排序
for(int j=i+1; j<=n; j++) {
if(x[i]>x[j]) {
swap(x[i],x[j]);
swap(y[i],y[j]);
}
}
}
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
p[i][j]=p[j][i] = length(x[i],y[i],x[j],y[j]);//计算两点间距离
d[1][1]=0;
for(int i=2; i<=n; i++)
d[i][1]=p[i][1];
for(int i=2; i<n; i++) {
d[i+1][i]=1000;//从第i+1个点到第一个点再回到第i个点的距离，先初始化为一个很大的值
for(int j=1; j<=i-1; j++) {
d[i+1][j]=d[i][j]+p[i][i+1];
d[i+1][i]=min(d[i+1][i],d[i][j]+p[j][i+1]);
}
}
cout<<setiosflags(ios::fixed)<<setprecision(2)<<d[n][n-1]+p[n][n-1]<<endl;
return 0;
}⭐️乘法表问题
❀题面：
定义于字母表Σ={a,b,c}上的乘法表如下
依此乘法表，对任一定义于Σ上的字符串，适当加括号后得到一个表达式。例如，对于字符串 x=bbbba，它的一个加括号表达式为(b(bb))(ba)。依乘法表，该表达式的值为 a。试设计一个动态规划算法，对任一定义于Σ上的字符串blob.png，计算有多少种不同的加括号方式，使由 x 导出的加括号表达式的值为 a。
算法设计：对于给定的字符串 blob.png，计算有多少种不同的加括号方式，使由 x 导出的加括号表达式的值为 a
【输入形式】
输入数据：第 1 行中给出一个字符串。
【输出形式】
将计算结果输出：第 1 行中的数是计算出的加括号方式数。
【样例输入】
bbbba
【样例输出】
6
❀代码&注释：
/*
--------------------------------------
--------Problem: 8919.乘法表问题------
------------------Author-------------
------------------XZITXX-------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn=50;
int result[maxn][maxn][3]={0};
int main()
{
ios::sync_with_stdio(false);
int len;//字符串的长度
string str;
cin>>str;
len=str.size();
for(int i=1; i<=len; i++)
{
//初始化
if(str[i-1]=='a') result[i][i][0]=1;
else result[i][i][0]=0;
if(str[i-1]=='b') result[i][i][1]=1;
else result[i][i][1]=0;
if(str[i-1]=='c') result[i][i][2]=1;
else result[i][i][2]=0;
}
for(int r=2; r<=len; r++)
{//接着从长度为 2 的子字符串计算，直至计算好整串 str
for(int i=1; i<=len-r+1; i++)
{
int j = i+r-1;//计算str[i:j]
for (int k=i; k<=j; k++)
{//根据题目中的表，计算加括号法
result[i][j][0] += result[i][k][0] * result[k + 1][j][2] + result[i][k][1] * result[k + 1][j][2] + result[i][k][2] * result[k + 1][j][0];
result[i][j][1] += result[i][k][0] * result[k + 1][j][0] + result[i][k][0] * result[k + 1][j][1] + result[i][k][1] * result[k + 1][j][1];
result[i][j][2] += result[i][k][1] * result[k + 1][j][0] + result[i][k][2] * result[k + 1][j][1] + result[i][k][2] * result[k + 1][j][2];
}
}
}
cout << result[1][len][0] << endl;
return 0;
}⭐️圈乘运算问题
❀题面：
关于整数的 2 元圈乘运算⊗定义为（X⊗Y）=10 进制整数 X 的各位数字之和 * 10 进制整数 Y 的最大数字+Y 的最小数字。例如,（9⊗30）=9*3+0=27。对于给定的 10 进制整数 X 和 K，由 X 和⊗运算可以组成各种不同的表达式。试设计一个算法，计算出由 X 和⊗运算组成的值为 K 的表达式最少需用多少个⊗运算。
算法设计：给定 10 进制整数 X 和 K (1≤X,K≤1020) ，计算由 X 和⊗运算组成的值为 K 的表达式最少需用多少个⊗运算
【输入形式】
输入数据：每一行有 2 个 10 进制整数 X 和 K。最后一行是 0 0（以0 0结束）。
【输出形式】
将找到的最少⊗运算个数输出。
【样例输入】
3 12
0 0
【样例输出】
1
这题TLE了
❀代码&注释：
/*
--------------------------------------
-----------8911. 圈乘运算问题---------
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX=81*30+9,MIN=-1;
int NumLen(int x){//统计位数
int len = 0;
while (x>0){
len++;
x /= 10;
}
return len;
}
void Init(int* a, int x){//作初始化
int min = 10;
int max = 0;
int num = 0;
int tend = 0;
while (x > 0){
tend = x % 10;
x /= 10;
num += tend;
if (tend > max){
max = tend;
}
if (tend < min){
min = tend;
}
}
a[0] = MAX;//存放最小圈乘次数
a[1] = num;//存放各位数之和
a[2] = min;//存放最小的数
a[3] = max;//存放最大的数
}
int main()
{
int x,k;
while(~scanf("%d%d",&x,&k)&&x!=0&&k!=0)
{
int n = NumLen(x);//表示x的位数
int m = 81*n+9;//b最小可以2为数组合，最大为9，最小为9.所以（x的各位数相加）*9+9；x的各位数相加最大为9*n；
if(m<177){//因为y可能是2位数，导致1位数的x圈乘后的结果为2位数
m = 177;
}
if (k>m){//若k大于x的最大圈乘数则退出
return -1;
}
int** r = new int*[m+2];//建立二维数组
for (int i=0; i<m+1; i++){//遍历每
r[i] = new int[4];
Init(r[i],i);
}
r[m+1] = new int[4];
Init(r[m+1], x);//将起始x写到数组的最后
r[m+1][0] = 0;//变成自己不需要圈乘
//开始操作
int flag = 1;
while (flag){//不断在序列中更新
flag = 0;
for (int i=1; i<=m+1; i++){//寻找X
if (r[i][0] < MAX){
for (int j=1; j<=m+1; j++){//寻找Y
if (r[j][0] < MAX){
int tend = r[i][1] * r[j][3] + r[j][2];//计算圈乘结果
if (r[tend][0]>r[i][0]+r[j][0]+1){//与原来的圈乘生产该数的次数对比找最小
flag = 1;//若有变化则更新x的寻值
r[tend][0] = r[i][0] + r[j][0] + 1; //r[i][0]为得到x的圈乘次数,r[j][0]位得到y的圈乘次数
}//endif
}//endif
}
}//endif
}
}
cout << r[k][0] << endl;
}
return 0;
}☀️【专题】回溯与分支限界
⭐️最小长度电路板排列问题
❀题面：
最小长度电路板排列问题是大规模电子系统设计中提出的实际问题。该问题的提法是， 将 n 块电路板以最佳排列方案插入带有 n 个插槽的机箱中。n 块电路板的不同的排列方式对 应于不同的电路板插入方案。 设 B={1，2，…，n }是 n 块电路板的集合。集合 L={ N1， N2 ，…， N m }是 n 块电路 板的 m 个连接块。其中每个连接块 Ni 是 B 的一个子集，且 Ni 中的电路板用同一根导线连 接在一起。 例如，设 n=8，m=5。给定 n 块电路板及其 m 个连接块如下： B={1，2，3，4，5，6，7，8}；L={ N1， N2 ， N3 ， N4 ， N5 }； N1 ={4，5，6}； N2 ={2，3}； N3 ={1，3}； N4 ={3，6}； N5 ={7，8}。 这 8 块电路板的一个可能的排列如图所示
在最小长度电路板排列问题中，连接块的长度是指该连接块中第 1 块电路板到最后 1 块电路板之间的距离。例如在图示的电路板排列中，连接块 N4 的第 1 块电路板在插槽 3 中， 它的最后 1 块电路板在插槽 6 中，因此 N4 的长度为 3。同理 N2 的长度为 2。图中连接块最 大长度为 3。试设计一个分支限界法找出所给 n 个电路板的最佳排列，使得 m 个连接块中最 大长度达到最小。
对于给定的电路板连接块，设计一个队列式分支限界法，找出所给 n 个电路板的最佳排 列，使得 m 个连接块中最大长度达到最小。
【输入形式】
第一行有 2 个正整数 n 和 m (1≤m,n≤20)。接下来的 n 行中，每行有 m 个数。第 k 行的第 j 个数为 0 表示电路板 k 不在连接块 j 中，1 表示电路板 k 在连接块 j 中。
【输出形式】
将计算出的电路板排列最小长度及其最佳排列输出。
文件的第 1 行是 最小长度；接下来的 1 行是最佳排列。
【样例输入】
8 5
1 1 1 1 1
0 1 0 1 0
0 1 1 1 0
1 0 1 1 0
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 0 0 1
【样例输出】
4
5 4 3 1 6 2 8 7
❀代码&注释：
/*最小长度电路板排列问题*/
#pragma GCC optimize(2 , "Ofast" , "inline")
#include <bits/stdc++.h>
using namespace std;
int n,m,**arr,*a;
int minlength=100000,templength;
int lef,rig,*opt;
int dfs(int t)
{
int i,j,temp;
if(t==n)
{
templength = 0;
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
if(arr[a[j]][i] == 1) {lef = j; break;}
for(j=n-1; j>=0; j--)
if(arr[a[j]][i] == 1) {rig = j; break;}
if(templength<rig-lef) templength = rig - lef;
}
if(minlength>templength) {
minlength = templength;
for(i=0; i<n; i++) opt[i] = a[i]+1;
}
}
for(i=t; i<n; i++)
{
temp = a[i];
a[i] = a[t];
a[t] = temp;
dfs(t+1);
temp = a[i];
a[i] = a[t];
a[t] = temp;
}
return 0;
}
int main()
{
scanf("%d %d",&n,&m);
a = (int*)malloc(n*sizeof(int));
opt = (int*)malloc(n*sizeof(int));
arr = (int **) malloc(n*sizeof(int *));//申请一组一维指针空间。
for(int i=0; i<n; i++)
arr[i] = (int *)malloc(m*sizeof(int)); //对于每个一维指针，申请一行数据的空间。
for(int i=0; i<n; i++) a[i] = i;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++) scanf("%d",&arr[i][j]);
dfs(0);
printf("%d\n",minlength);
for(int i=0; i<n; i++) printf("%d ",opt[i]);
return 0;
}⭐️圆排列问题
❀题面：
算法设计：对于给定的 n 个圆，设计一个优先队列式分支限界法，计算 n 个圆的最佳排列方案，使其长度达到最小
【输入形式】
输入数据。第一行有 1 个正整数 n (1≤n≤20)。接下来的 1 行有 n个数，表示 n 个圆的半径。
【输出形式】
将计算出的最小圆排列的长度输出。
【样例输入】
3
1 1 2
【样例输出】
7.65685
❀代码&注释：
#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE=100;
int N;
double minlen = 10000, x[MAX_SIZE], r[MAX_SIZE];//分别为最小圆排列长度，每个圆心横坐标，每个圆半径
double bestr[MAX_SIZE];//最小圆排列的半径顺序
//计算圆心横坐标
double center(int t)//得到每个圆的圆心坐标
{
double temp = 0;
for (int j=1; j<t; ++j)//因为目标圆有可能与排在它之前的任一圆相切，故需一一判断
{
double xvalue = x[j] + 2.0*sqrt(r[t]*r[j]);
temp = max(xvalue, temp);
}
return temp;
}
//计算圆排列长度
void compute()
{
double low=0, high=0;
for(int i=1; i<N; ++i)
{
low = min(low, x[i]-r[i]);
high = max(x[i] + r[i], high);
}
if(high-low < minlen)
{
minlen = high - low;
for (int i=1; i<N; ++i) bestr[i] = r[i];
}
}
//回溯算法
void backtrack(int t)
{
if (t == N)
{
compute();//计算圆排列长度
return;
}
for (int j = t; j < N; ++j)
{
swap(r[t], r[j]);
double centerx = center(t);
if (centerx + r[t] + r[1] < minlen)
{
x[t] = centerx;
backtrack(t + 1);//到第t+1个圆
}
swap(r[t], r[j]);//恢复状态
}
}
int main()
{
cin >> N;
N++;
for(int i=1; i<N; i++) cin >> r[i];
backtrack(1);
cout << minlen << endl;
return 0;
}⭐️推箱子问题
❀题面：
码头仓库是划分为 n×m 个格子的矩形阵列。有公共边的格子是相邻格子。当前仓库中有的格子是空闲的；有的格子则已经堆放了沉重的货物。由于堆放的货物很重，单凭仓库管理员的力量是无法移动的。仓库管理员有一项任务，要将一个小箱子推到指定的格子上去。管理员可以在仓库中移动，但不能跨过已经堆放了货物的格子。管理员站在与箱子相对的空闲格子上时，可以做一次推动，把箱子推到另一相邻的空闲格子。推箱时只能向管理员的对面方向推。由于要推动的箱子很重，仓库管理员想尽量减少推箱子的次数。
对于给定的仓库布局，以及仓库管理员在仓库中的位置和箱子的开始位置和目标位置，设计一个解推箱子问题的分支限界法，计算出仓库管理员将箱子从开始位置推到目标位置所需的最少推动次数。
【输入形式】
输入数据的第1 行有2个正整数n和m（1<=n,m<=100），表示仓库是n×m个格子的矩形阵列。接下来有n行，每行有m个字符，表示格子的状态。
S 表示格子上放了不可移动的沉重货物；
w 表示格子空闲；
M 表示仓库管理员的初始位置；
P 表示箱子的初始位置；
K 表示箱子的目标位置。
【输出形式】
将计算出的最少推动次数输出。如果仓库管理员无法将箱子从开始位置推到目标位置则输出“No solution！”
【样例输入】
10 12
SSSSSSSSSSSS
SwwwwwwwSSSS
SwSSSSwwSSSS
SwSSSSwwSKSS
SwSSSSwwSwSS
SwwwwwPwwwww
SSSSSSSwSwSw
SSSSSSMwSwww
SSSSSSSSSSSS
SSSSSSSSSSSS
【样例输出】
7
❀详细思路过程&代码&注释&优化：
❀优化后代码：
#include <bits/stdc++.h>
#define ll long long
#include <queue>
using namespace std;
int n,m,manx,many,sx,sy,ex,ey;
char x;
int tu[102][102];
int steps[102][102][4];
bool usedmark[102][102][4];
struct yz {
int x,y,type;
bool friend operator < (yz x,yz y) {
int d1=abs(x.x-ex)+abs(x.y-ey)+steps[x.x][x.y][x.type];
int d2=abs(y.x-ex)+abs(y.y-ey)+steps[y.x][y.y][y.type];
return d1>d2;
}
}q[100001],p[10001];
bool in_it(int x,int y) {
if(x<=0 || x>n) return false;
if(y<=0 || y>m) return false;
return true;
}
int oneNumInBinary(ll n) { // 求十进制数的二进制中1的个数
ll cnt=0;
while(n) n=n&(n-1),cnt++;
// 或者 while(n) cnt+=n%2, n/=2; 容易理解一些
return cnt;
}
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
bool mark[102][102];
priority_queue<yz> que;
void read(ll &x){
char ch=getchar();
x=0;
for (; ch<'0' || ch>'9'; ch=getchar());
for (; ch>='0' && ch<='9'; ch=getchar()) x=x*10+ch-'0';
}
void initial_steps(int sx,int sy,int boxx,int boxy ) {
memset(usedmark,false,sizeof(usedmark));
memset(steps,63,sizeof(steps));
int cnt=1;
q[cnt].x=sx;
q[cnt].y=sy;
int l=1,r=1,nowx,nowy;
memset(mark,false,sizeof(mark));
mark[sx][sy]=true;
mark[boxx][boxy]=true;
while(l<=r) {
for(int i=0; i<4; i++) {
nowx=q[l].x+dx[i];
nowy=q[l].y+dy[i];
if(!tu[nowx][nowy] && in_it(nowx,nowy) && !mark[nowx][nowy]) {
mark[nowx][nowy]=true;
q[++r].x=nowx; q[r].y=nowy;
}
}
l++;
}
for(int i=0; i<4; i++) {
nowx=boxx+dx[i];
nowy=boxy+dy[i];
if(!tu[nowx][nowy] && in_it(nowx,nowy) && mark[nowx][nowy])
steps[boxx][boxy][i]=0;
}
}
ll qpow(ll a,ll b) {
ll ans=1;
while(b) {
if(b&1) ans=(ans*a)%999;
a=a*a%999;
b>>=1;
}
return ans;
}
void inter_bfs(int sx,int sy,int type,int &righ,int step) {
if(usedmark[sx][sy][type]) return;
usedmark[sx][sy][type]=true;
int l=1,r=1;
int nowx=sx+dx[type];
int nowy=sy+dy[type];
p[l].x=nowx;
p[l].y=nowy;
memset(mark,false,sizeof(mark));
mark[nowx][nowy]=true;
mark[sx][sy]=true;
while(l<=r) {
for(int i=0; i<4; i++) {
nowx=p[l].x+dx[i];
nowy=p[l].y+dy[i];
if(in_it(nowx,nowy) && !mark[nowx][nowy] && !tu[nowx][nowy]) {
r++;
mark[nowx][nowy]=true;
p[r].x=nowx; p[r].y=nowy;
}
}l++;
}
yz w;
for(int i=0; i<4; i++) {
if(i!=type) {
nowx=sx+dx[i];
nowy=sy+dy[i];
if(in_it(nowx,nowy) && mark[nowx][nowy] && !tu[nowx][nowy]) {
if(step<steps[sx][sy][i]) {
steps[sx][sy][i]=step;
w.x=sx;
w.y=sy;
w.type=i;
que.push(w);
usedmark[sx][sy][i]=true;
}
}
}
}
return;
}
void bfs() {
int l=1,r=0,lx,ly,ltype;
yz w;
for(int i=0; i<4; i++)
{
if(steps[sx][sy][i]==0 && in_it(sx+dx[i],sy+dy[i])) {
w.x=sx;
w.y=sy;
w.type=i;
que.push(w);
}
}
int nowx,nowy;
while(que.size()) {
yz tp=que.top();
que.pop();
lx=tp.x;
ly=tp.y;
ltype=tp.type;
nowx=lx-dx[ltype];
nowy=ly-dy[ltype];
if(in_it(nowx,nowy) && !tu[nowx][nowy] && steps[lx][ly] [ltype]+1<=steps[nowx][nowy][ltype]) {
w.x=nowx;
w.y=nowy;
w.type=ltype;
que.push(w);
steps[nowx][nowy][ltype]=steps[lx][ly][ltype]+1;
if(nowx==ex && nowy==ey) {
cout<<steps[nowx][nowy][ltype]<<endl;
return;
}
}
inter_bfs(lx,ly,ltype,r,steps[lx][ly][ltype]);
l++;
}
cout<<"No solution!"<<endl;
}
int main()
{
cin>>n>>m;
string s;
for(int i=1; i<=n; i++) {
cin>>s;
for(int j=0; j<m; j++) {
x=s[j];
if(x=='S') tu[i][j+1]=1;
else if(x=='M') {
manx=i;
many=j+1;
}
else if(x=='P') {
sx=i;
sy=j+1;
}
else if(x=='K') {
ex=i;
ey=j+1;
}
}
}
initial_steps(manx,many,sx,sy);
bfs();
return 0;
}算法设计与分析之 “贪心” 经典习题总结&AC代码_夏旭的博客-CSDN博客
算法设计与分析之 “递归与分治” 经典习题总结&AC代码_夏旭的博客-CSDN博客
算法设计与分析之 “动态规划” 经典习题总结&AC代码_夏旭的博客-CSDN博客文章来源：https://www.toymoban.com/news/detail-492447.html
算法设计与分析之 “回溯与分支限界法” 经典习题总结&AC代码_夏旭的博客-CSDN博客文章来源地址https://www.toymoban.com/news/detail-492447.html
到了这里，关于【算法设计与分析】经典常考三十三道例题&AC代码的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
