?小蝦目前大三，我校在大一下開設(shè)《數(shù)據(jù)結(jié)構(gòu)》這門課，大二上開了《算法設(shè)計(jì)與分析》這門課，很慶幸這兩門課的上機(jī)考試總成績(jī)一門100，一門99，最后總分也都90+。下文會(huì)給出機(jī)試的33道題目＆AC代碼＆注釋供大家參考。

?《算法設(shè)計(jì)與分析》用的是屈婉玲老師的教材，上機(jī)習(xí)題用的是王曉東前輩的，開授這門課的教授表示：考慮到算法具有一定的難度，并不適合所有的學(xué)生，只講授和考察四個(gè)專題的內(nèi)容（貪心、遞歸與分治、動(dòng)態(tài)規(guī)劃、回溯與分值限界）

?課程考核主要分為平時(shí)練習(xí)、多次機(jī)試和最后的筆試（卷面考試），筆試大概主要是考察結(jié)合問題情景設(shè)計(jì)算法，寫出偽代碼并進(jìn)行相應(yīng)的分析。每個(gè)專題限時(shí)開放若干道機(jī)試練習(xí)題，不給出答案，后面的機(jī)試就是給出里面的題目進(jìn)行考核，按測(cè)試點(diǎn)給分（會(huì)有少部分測(cè)試點(diǎn)改成大數(shù)或特例）。

?廢話不多說，下面將四大專題的 習(xí)題&答案 分享給大家，希望能提供力所能及的幫助，原創(chuàng)不易，感謝支持！

之前按照專題分類發(fā)布過，這次作為一個(gè)合集發(fā)布，于人于己提供方便~ 對(duì)應(yīng)的專題鏈接也會(huì)放在文末。

?轉(zhuǎn)載隨意，但請(qǐng)注明出處！

??【專題】貪心

??外幣兌換問題

?題面：

外幣兌換是指利用貨幣匯兌率的差異將一個(gè)單位的某種貨幣轉(zhuǎn)換為大于一個(gè)單位的同種貨幣。例如，假定 1 美元可以買 0.7 英鎊，1 英鎊可以買 9.5 法郎，且 1 法郎可以買到 0.16 美元。通過貨幣兌換，一個(gè)商人可以從 1 美元開始買入，得到 0.7×9.5×0.16=1.064 美元，從而獲得 6.4%的利潤(rùn)。

算法設(shè)計(jì)：給定 n 種貨幣c1,c2,...,cn的有關(guān)兌換率，試設(shè)計(jì)一個(gè)有效算法，用以確定是否存在有收益的兌換可能。

【輸入形式】
輸入數(shù)據(jù)：輸入數(shù)據(jù)含有多個(gè)測(cè)試數(shù)據(jù)項(xiàng)：每個(gè)測(cè)試數(shù)據(jù)的第一行中只有1個(gè)整數(shù)n(1<=n<=30)，表示貨幣總種類數(shù)。其后n行給出n種貨幣的名稱。接下來的一行中有1個(gè)整數(shù)m，表示有m種不同的貨幣兌換率。其后m行給出m種不同的貨幣兌換率，每行有3個(gè)數(shù)據(jù)項(xiàng)ci，rij和cj，表示貨幣ci和cj的兌換率為rij。每個(gè)測(cè)試數(shù)據(jù)項(xiàng)以空行分隔(測(cè)試數(shù)據(jù)以0結(jié)束)。
【輸出形式】
對(duì)每個(gè)測(cè)試數(shù)據(jù)項(xiàng)，如果存在套匯的可能性則輸出“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來處理貨幣對(duì)應(yīng)的下標(biāo)
? ? ? ? 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個(gè)t2.
? ? ? ? }
? ? ? ? Flody();
? ? ? ? int flag = 1;
? ? ? ? for(int i=1; i<=n; i++)
? ? ? ? {
? ? ? ? ? ? if(Map[i][i]>1) ?///如果第i種貨幣經(jīng)過來回兌換后，比原來錢多了，則就可以通過這樣的方式賺到錢
? ? ? ? ? ? {
? ? ? ? ? ? ? ? printf("Case %d Yes\n",++t);
? ? ? ? ? ? ? ? flag = 0;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(flag) ///代表無論如何兌換，都會(huì)賠本，則輸出No.
? ? ? ? ? ? printf("Case %d No\n",++t);
? ? }
? ? return 0;
}

??磁盤文件最優(yōu)存儲(chǔ)問題

?題面：

【輸出形式】
將計(jì)算出的最小期望檢索時(shí)間輸出。

【樣例輸入】
5?
33 55 22 11 9
【樣例輸出】
0.547396

?代碼&注釋：

/*
--------------------------------------
------Problem: 磁盤文件最優(yōu)存儲(chǔ)問題---
------------------Author--------------
------------------XZITXX--------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long?
using namespace std;
bool cmp(int a,int b){return a>b;}

/*將數(shù)組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++) {//數(shù)組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];//經(jīng)變化后的a數(shù)組
}

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。計(jì)算它們的磁道間的檢索時(shí)間
? ? ? ? ? ? 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;
}

??會(huì)場(chǎng)安排問題

?題面：

假設(shè)要在足夠多的會(huì)場(chǎng)里安排一批活動(dòng)，并希望使用盡可能少的會(huì)場(chǎng)。設(shè)計(jì)一個(gè)有效的算法進(jìn)行安排，求出最少需要的會(huì)場(chǎng)數(shù)。

算法設(shè)計(jì)：對(duì)于給定的 k 個(gè)待安排的活動(dòng)，計(jì)算使用最少會(huì)場(chǎng)的時(shí)間表。

【輸入形式】
輸入數(shù)據(jù):第一行有 1 個(gè)正整數(shù) k，表示有 k 個(gè)待安排的活動(dòng)。接下來的 k 行中，每行有 2 個(gè)正整數(shù)，分別表示 k 個(gè)待安排的活動(dòng)開始時(shí)間和結(jié)束時(shí)間。時(shí)間以 0 點(diǎn)開始的分鐘計(jì)。
【輸出形式】
將計(jì)算出的最少會(huì)場(chǎng)數(shù)輸出?！緲永斎搿?br> 5
1 23
12 28
25 35
27 80
36 50
【樣例輸出】
?3

?代碼&注釋：

/*
--------------------------------------
------------Problem: 會(huì)場(chǎng)安排問題-----
------------------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;
}

??非單位時(shí)間任務(wù)安排問題

?題面：

【樣例輸入】
7?
1 4 70?
2 2 60?
1 4 50?
1 3 40?
1 1 30?
1 4 20?
3 6 80

【樣例輸出】
110

?代碼&注釋：

/*
--------------------------------------
-----Problem: 非單位時(shí)間任務(wù)安排問題--
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long?
using namespace std;
int n;//任務(wù)個(gè)數(shù)?

struct task{
?? ?int t;//任務(wù)時(shí)間
?? ?int d;//截止時(shí)間
?? ?int w;//懲罰時(shí)間?
};?
task a[100];

int bestw;//存儲(chǔ)最短的任務(wù)懲罰時(shí)間
int w;//當(dāng)前的任務(wù)懲罰時(shí)間
int t;//當(dāng)前所做任務(wù)總時(shí)間?
int x[100];?

void backtrack(int i)
{
?? ?if(i>n)//到達(dá)葉節(jié)點(diǎn)?
?? ?{bestw=w;return;}?
?? ?/*約束條件：所做任務(wù)總時(shí)間是否<=當(dāng)前任務(wù)截止時(shí)間，成立進(jìn)入左子樹*/
?? ?if(t+a[i].t<=a[i].d)?
?? ?{?? ?
?? ??? ?t+=a[i].t;//更新總時(shí)間?
?? ??? ?backtrack(i+1);
?? ??? ?t-=a[i].t;//回溯結(jié)束時(shí)時(shí)間要還原?
?? ?}?
?? ?/*限界函數(shù)：當(dāng)前總懲罰是否<=bestw，成立進(jìn)入右子樹，否則剪枝*/?
?? ?if(w+a[i].w<=bestw)?
?? ?{
?? ??? ?w=w+a[i].w;
?? ??? ?backtrack(i+1);
?? ??? ?w=w-a[i].w;
?? ?}
}

int main()
{
?? ?cin>>n;//輸入任務(wù)個(gè)數(shù)
?? ?w=0;t=0;bestw=1000;//先將bestw設(shè)置為一個(gè)較大的值?
?? ?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的錢至少需要的硬幣個(gè)數(shù)
int dp[N]; // dp[i]為當(dāng)前擁有的硬幣數(shù)量條件下表示面值為i的最少硬幣個(gè)數(shù)
int value[6] = {1,2,4,10,20,40}; // 每種硬幣對(duì)應(yīng)面值，依次為1，2,4,10,20,40個(gè)五分，即5,10,20,50,100,200；
int number[6]; // 對(duì)應(yīng)于當(dāng)前擁有的每種硬幣個(gè)數(shù)

void init() // 計(jì)算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(); //計(jì)算出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++) //計(jì)算顧客支付面值i需要的最少硬幣數(shù)dp[i]
? ? ? ? {
? ? ? ? ? ? while(number[i]--) //將混合背包拆成01背包做，寫水了點(diǎn)。。。
? ? ? ? ? ? {
? ? ? ? ? ? ? ? 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個(gè)加油站
? ? 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) {//車無法達(dá)到第i個(gè)加油站,加油一次，s等于從加過油的地方開始計(jì)
? ? ? ? ? ? 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塔問題

?題面：

設(shè)A、B、C 是3 個(gè)塔座。開始時(shí)，在塔座A 上有一疊共n 個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1，2，……，n，奇數(shù)號(hào)圓盤著紅色，偶數(shù)號(hào)圓盤著藍(lán)色，如圖所示?，F(xiàn)要求將塔座A 上的這一疊圓盤移到塔座B 上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：?

規(guī)則(1)：每次只能移動(dòng)1 個(gè)圓盤；?
規(guī)則(2)：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上；?
規(guī)則(3)：任何時(shí)刻都不允許將同色圓盤疊在一起；?
規(guī)則(4)：在滿足移動(dòng)規(guī)則(1)-(3)的前提下，可將圓盤移至A，B，C 中任一塔座上。

試設(shè)計(jì)一個(gè)算法，用最少的移動(dòng)次數(shù)將塔座A 上的n 個(gè)圓盤移到塔座B 上，并仍按同樣順序疊置。對(duì)于給定的正整數(shù)n，計(jì)算最優(yōu)移動(dòng)方案。?

?
【輸入形式】
輸入數(shù)據(jù)：第1 行是給定的正整數(shù)n。
【輸出形式】
將計(jì)算出的最優(yōu)移動(dòng)方案輸出：文件的每一行由一個(gè)正整數(shù)k 和2 個(gè)字符c1 和c2 組成，表示將第k 個(gè)圓盤從塔座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;
}

??半數(shù)集問題

?題面：

給定一個(gè)自然數(shù)n，由n 開始可以依次產(chǎn)生半數(shù)集set(n)中的數(shù)如下。
(1) n∈set(n)；
(2) 在n 的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超過最近添加的數(shù)的一半；
(3) 按此規(guī)則進(jìn)行處理，直到不能再添加自然數(shù)為止。
例如，set(6)={6,16,26,126,36,136}。半數(shù)集set(6)中有6 個(gè)元素。
注意半數(shù)集是多重集。

? 算法設(shè)計(jì)：對(duì)于給定的自然數(shù)n，計(jì)算半數(shù)集set(n)中的元素個(gè)數(shù)。

【輸入形式】
輸入數(shù)據(jù)：每個(gè)數(shù)據(jù)只有1 行，給出整數(shù)n。(0<n<1000)（輸入數(shù)據(jù)有多行）
【輸出形式】
結(jié)果輸出：輸出的每一行是半數(shù)集set(n)中的元素個(gè)數(shù)。

【樣例輸入】
6
【樣例輸出】
6

?代碼&注釋：

/*
--------------------------------------
--------Problem: 8777.半數(shù)集問題------
------------------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;
}

??整數(shù)因子分解問題

?題面：

大于1 的正整數(shù)n可以分解為：n=x1 * x2*…*xm。
例如，當(dāng)n=12 時(shí)，共有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

算法設(shè)計(jì)：對(duì)于給定的正整數(shù)n，計(jì)算n共有多少種不同的分解式。

【輸入形式】
? ? 1 個(gè)正整數(shù)n (1≤n≤2000000000)。
【輸出形式】
將計(jì)算出的不同的分解式數(shù)輸出。

【樣例輸入】
12
【樣例輸出】
8

?代碼&注釋：

/*
--------------------------------------
-----Problem: 8779.整數(shù)因子分解問題---
-----------------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)//采用了動(dòng)態(tài)規(guī)劃思想，由于本題數(shù)據(jù)量大，遞歸會(huì)超時(shí)
{
?? ?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];//講大問題逐步轉(zhuǎn)化成一個(gè)個(gè)小問題
?? ?}
}
?
int main()
{
?? ?int n;
?? ?cin >> n;?
?? ?ul(n);//找n的因子有哪些，并存放到數(shù)組a中
?? ?sort(a, a+k);//注意這個(gè)地方，將a有小到大排列起來
?? ?solve(n);
?? ?printf("%d\n", dp[k-1]);
?? ?return 0;
}

??排列的字典序問題

?題面：

n個(gè)元素{1,2,..., n }有n!個(gè)不同的排列。將這n!個(gè)排列按字典序排列，并編號(hào)為0，1，…，n!-1。每個(gè)排列的編號(hào)為其字典序值。例如，當(dāng)n=3時(shí)，6 個(gè)不同排列的字典序值如下：
字典序值?? ?0?? ?1?? ?2?? ?3?? ?4?? ?5
排列?? ?123?? ?132?? ?213?? ?231?? ?312?? ?321

算法設(shè)計(jì)：給定n以及n個(gè)元素{1,2,..., n }的一個(gè)排列，計(jì)算出這個(gè)排列的字典序值，以及按字典序排列的下一個(gè)排列。

【輸入形式】
數(shù)據(jù)的第1 行是元素個(gè)數(shù)n。接下來的1 行是n個(gè)元素{1,2,?, n }的一個(gè)排列。
【輸出形式】
將計(jì)算出的排列的字典序值和按字典序排列的下一個(gè)排列輸出：輸出的第一行是字典序值，第2行是按字典序排列的下一個(gè)排列。

【樣例輸入】
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;
}

??眾數(shù)問題

?題面：

給定含有n個(gè)元素的多重集合S，每個(gè)元素在S中出現(xiàn)的次數(shù)稱為該元素的重?cái)?shù)。多重集S中重?cái)?shù)最大的元素稱為眾數(shù)。例如，S={1，2，2，2，3，5}。多重集S的眾數(shù)是2，其重?cái)?shù)為3。

算法設(shè)計(jì)：對(duì)于給定的由n 個(gè)自然數(shù)組成的多重集S，計(jì)算S的眾數(shù)及其重?cái)?shù)。

【輸入形式】
輸入數(shù)據(jù)：第1行多重集S中元素個(gè)數(shù)n；接下來的n行中，每行有一個(gè)自然數(shù)。
【輸出形式】
? 輸出的第1行給出眾數(shù)，第2 行是重?cái)?shù)。

【樣例輸入】
6
1
2
2
2
3
5
【樣例輸出】
2
3

?代碼&注釋：

/*
--------------------------------------
-----------Problem: 8783.眾數(shù)問題-----
--------------------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;
}

??輸油管道問題

?題面：

某石油公司計(jì)劃建造一條由東向西的主輸油管道。該管道要穿過一個(gè)有n 口油井的油田。從每口油井都要有一條輸油管道沿最短路經(jīng)(或南或北)與主管道相連。如果給定n口油井的位置,即它們的x 坐標(biāo)（東西向）和y 坐標(biāo)（南北向）,應(yīng)如何確定主管道的最優(yōu)位置,即使各油井到主管道之間的輸油管道長(zhǎng)度總和最小的位置?證明可在線性時(shí)間內(nèi)確定主管道的最優(yōu)位置。

算法設(shè)計(jì)：給定 n 口油井的位置,計(jì)算各油井到主管道之間的輸油管道最小長(zhǎng)度總和。

【輸入形式】
輸入數(shù)據(jù)：第1 行是油井?dāng)?shù)n，1<=n<=10000。接下來n 行是油井的位置，每行2個(gè)整數(shù)x和y，-10000<=x，y<=10000。
【輸出形式】
輸出數(shù)據(jù)的第1 行中的數(shù)是油井到主管道之間的輸油管道最小長(zhǎng)度總和。

【樣例輸入】
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)//找到中位數(shù)
? ? ? ? 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);//算出長(zhǎng)度之和

? ? printf("%d\n",ans);
? ? return 0;
}

??集合劃分問題

?題面：

n個(gè)元素的集合{1,2,...., n }可以劃分為若干個(gè)非空子集。例如，當(dāng)n=4 時(shí)，集合{1，2，3，4}可以劃分為15 個(gè)不同的非空子集如下：
{{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}}

算法設(shè)計(jì)：給定正整數(shù) n，計(jì)算出n個(gè)元素的集合{1,2,..., n }可以劃分為多少個(gè)不同的非空子集。

【輸入形式】
輸入數(shù)據(jù):第1 行是元素個(gè)數(shù)n。
【輸出形式】
將計(jì)算出的不同的非空子集數(shù)輸出.

【樣例輸入】
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 個(gè)元素的集合{1,2,..., n }可以劃分為若干個(gè)非空子集。例如，當(dāng)n=4 時(shí)，集合{1，2，3，4}可以劃分為15 個(gè)不同的非空子集如下：?
{{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 個(gè)子集組成；集合{{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 個(gè)子集組成；集合{{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 個(gè)子集組成；集合{{1}，{2}，{3}，{4}}由4 個(gè)子集組成。?

算法設(shè)計(jì)：?給定正整數(shù) n 和 m，計(jì)算出 n 個(gè)元素的集合{1,2,...., n }可以劃分為多少個(gè)不同的由m個(gè)非空子集組成的集合。?

【輸入形式】
輸入數(shù)據(jù):第1 行是元素個(gè)數(shù)n 和非空子集數(shù)m。
【輸出形式】
將計(jì)算出的不同的由m 個(gè)非空子集組成的集合數(shù)輸出。

【樣例輸入】
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;
}

??士兵站隊(duì)問題

?題面:

在一個(gè)劃分成網(wǎng)格的操場(chǎng)上，n個(gè)士兵散亂地站在網(wǎng)格點(diǎn)上。網(wǎng)格點(diǎn)由整數(shù)坐標(biāo)(x,y)表示。士兵們可以沿網(wǎng)格邊上、下、左、右移動(dòng)一步，但在同一時(shí)刻任一網(wǎng)格點(diǎn)上只能有一名士兵。按照軍官的命令，士兵們要整齊地列成一個(gè)水平隊(duì)列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何選擇x 和y的值才能使士兵們以最少的總移動(dòng)步數(shù)排成一列。

算法設(shè)計(jì)：計(jì)算使所有士兵排成一行需要的最少移動(dòng)步數(shù)。

【輸入形式】
輸入數(shù)據(jù):第1 行是士兵數(shù)n，1<=n<=10000。接下來n 行是士兵的初始位置，每行2 個(gè)整數(shù)x 和y，-10000<=x，y<=10000。
【輸出形式】
將計(jì)算結(jié)果:輸出的第1 行中的數(shù)是士兵排成一行需要的最少移動(dòng)步數(shù)。

【樣例輸入】
5
1 2
2 2
1 3
3 -2
3 3

【樣例輸出】
8

?代碼&注釋：

/*
---------------------------------------
-------Problem: 8789.士兵站隊(duì)問題------
------------------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;
}

??標(biāo)準(zhǔn)2維表問題

?題面：

設(shè) n 是一個(gè)正整數(shù)。2′n 的標(biāo)準(zhǔn)2 維表是由正整數(shù)1，2，…，2n 組成的2′n 數(shù)組，該數(shù)組的每行從左到右遞增，每列從上到下遞增。2′n的標(biāo)準(zhǔn)2 維表全體記為Tab(n)。例如，當(dāng)n=3時(shí)Tab(3)如下：

算法設(shè)計(jì)：給定正整數(shù)n，計(jì)算Tab(n)中2′n的標(biāo)準(zhǔn)2 維表的個(gè)數(shù)。

【輸入形式】
輸入數(shù)據(jù):第一行有1 個(gè)正整數(shù)n。
【輸出形式】
將計(jì)算出的Tab(n)中2′n的標(biāo)準(zhǔn)2 維表的個(gè)數(shù)輸出。

【樣例輸入】
3
【樣例輸出】
5

?代碼&注釋：

/*
--------------------------------------
------Problem: 8790.標(biāo)準(zhǔn)2維表問題-----
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define CARRYS 10000

int ?prmStatic(int *prm,int num) ?// 產(chǎn)生小于num的所有質(zhì)數(shù)。
{
? ? 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) ?//質(zhì)因數(shù)分解
{
? ? 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)//輸出結(jié)果
{
? ? 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 的國(guó)際象棋棋盤上的一只馬，恰好走過除起點(diǎn)外的其它 63 個(gè)位置各一次，最后回到起點(diǎn)。這條路線稱為一條馬的 Hamilton 周游路線。對(duì)于給定的 m* n 的國(guó)際象棋棋盤，m 和 n 均為大于 5 的偶數(shù)，且 |m-n|≤2，試設(shè)計(jì)一個(gè)分治算法找出一條馬的 Hamilton周游路線。對(duì)于給定的偶數(shù) m，n≥6，且 |m-n|≤2，計(jì)算m′n 的國(guó)際象棋棋盤一條馬的 Hamilton周游路線。

【輸入形式】
第一行有2個(gè)正整數(shù)m和n，表示給定的國(guó)際象棋棋盤由m行，每行n個(gè)格子組成。
【輸出形式】
將計(jì)算出的馬的Hamilton周游路線用下面的2 種表達(dá)方式輸出：
第1 種表達(dá)方式按照馬步的次序給出馬的Hamilton 周游路線。馬的每一步用所在的方格坐標(biāo)(x，y)來表示。x表示行的坐標(biāo)，編號(hào)為0，1，…，m-1；y表示列的坐標(biāo)，編號(hào)為0，1，…，n-1。起始方格為（0，0）。
第2 種表達(dá)方式在棋盤的方格中標(biāo)明馬到達(dá)該方格的步數(shù)。（0，0）方格為起跳步，并標(biāo)明為第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

實(shí)現(xiàn)的有點(diǎn)誤差，下面是代碼對(duì)應(yīng)的輸出：

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;
}

??【專題】動(dòng)態(tài)規(guī)劃

??最小 m 段和問題

?題面：

給定 n 個(gè)整數(shù)組成的序列，現(xiàn)在要求將序列分割為 m 段，每段子序列中的數(shù)在原序列
中連續(xù)排列。如何分割才能使這 m段子序列的和的最大值達(dá)到最小？

算法設(shè)計(jì)：給定 n 個(gè)整數(shù)組成的序列,計(jì)算該序列的最優(yōu) m 段分割，使 m 段子序列的和的最大值達(dá)到最小

【輸入形式】
輸入數(shù)據(jù)：第 1 行中有 2 個(gè)正整數(shù) n 和 m。正整數(shù) n 是序列的長(zhǎng)度；正整數(shù) m是分割的段數(shù)。接下來的一行中有 n 個(gè)整數(shù)。
【輸出形式】
將計(jì)算結(jié)果輸出：第 1 行中的數(shù)是計(jì)算出的 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 乘積問題

?題面：

設(shè) I 是一個(gè) n 位十進(jìn)制整數(shù)。如果將 I 劃分為 k 段，則可得到 k 個(gè)整數(shù)。這 k 個(gè)整數(shù)的
乘積稱為 I 的一個(gè) k 乘積。試設(shè)計(jì)一個(gè)算法，對(duì)于給定的 I 和 k，求出 I 的最大 k 乘積。

算法設(shè)計(jì)：對(duì)于給定的 I 和 k，計(jì)算 I 的最大 k 乘積。

【輸入形式】
輸入數(shù)據(jù)：第 1 行中有 2 個(gè)正整數(shù) n 和 k。正整數(shù) n 是序列
的長(zhǎng)度；正整數(shù) k 是分割的段數(shù)。
接下來的一行中是一個(gè) n 位十進(jìn)制整數(shù)。（n<=10）
【輸出形式】
將計(jì)算結(jié)果輸出：第 1 行中的數(shù)是計(jì)算出的最大 k 乘積。

【樣例輸入】
2 1
15
【樣例輸出】
15

?代碼&注釋：

/*
--------------------------------------
-----Problem: 8917.最大k乘積問題------
----------------Author---------------
----------------XZITXX---------------
--------------------------------------
*/

#include <bits/stdc++.h>
using namespace std;
int dp[15][15]; ? ? //最大乘積數(shù)組
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;
}

??最大長(zhǎng)方體問題

?題面：

一個(gè)長(zhǎng)，寬，高分別為 m,n,p 的長(zhǎng)方體被分割成個(gè) m*n*p 個(gè)小立方體。每個(gè)小立方體內(nèi)有一個(gè)整數(shù)。試設(shè)計(jì)一個(gè)算法，計(jì)算出所給長(zhǎng)方體的最大子長(zhǎng)方體。子長(zhǎng)方體的大小由它所含所有整數(shù)之和確定。

算法設(shè)計(jì)：對(duì)于給定的長(zhǎng)，寬，高分別為 m,n,p 的長(zhǎng)方體，計(jì)算最大子長(zhǎng)方體的大小

【輸入形式】
輸入數(shù)據(jù)：第 1 行是 3 個(gè)正整數(shù) m,n,p，1≤m,n,p≤50。接下來 m*n 行每行 p 個(gè)正整數(shù)，表示小立方體中的數(shù)。
【輸出形式】
將計(jì)算結(jié)果輸出：第 1 行中的數(shù)是計(jì)算出的最大子長(zhǎng)方體的大小。

【樣例輸入】
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.最大長(zhǎng)方體問題-----
---------------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++) {//動(dòng)規(guī)思想，將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);
}

??最少硬幣問題

?題面：

設(shè)有 n 種不同面值的硬幣，各硬幣的面值存于數(shù)組 T[1:n]中。現(xiàn)要用這些面值的硬幣來找錢?？梢允褂玫母鞣N面值的硬幣個(gè)數(shù)存于數(shù)組 Coins[1:n]中。對(duì)任意錢數(shù) 0≤m≤20001，設(shè)計(jì)一個(gè)用最少硬幣找錢 m 的方法。

算法設(shè)計(jì)：對(duì)于給定的 1≤n≤10，硬幣面值數(shù)組 T 和可以使用的各種面值的硬幣個(gè)數(shù)數(shù)組 Coins，以及錢數(shù) m，0≤m≤20001，計(jì)算找錢 m的最少硬幣數(shù)

【輸入形式】
輸入數(shù)據(jù)：第一行中只有 1 個(gè)整數(shù)給出n 的值,第 2 行起每
行 2 個(gè)數(shù)，分別是 T[j]和 Coins[j]。最后 1 行是要找的錢數(shù) m。
【輸出形式】
將計(jì)算出的最少硬幣數(shù)輸出。問題無解時(shí)輸出-1。

【樣例輸入】
3
1 3
2 3
5 3
18
【樣例輸出】
5

?代碼&注釋：

/*
--------------------------------------
------Problem: 8913.最少硬幣問題------
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/

/*多重背包(硬幣種類有限制，硬幣數(shù)目有限制)*/
#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;
? ? //錢數(shù)為dp[i]是的硬幣數(shù)目
? ? int *dp = new int[maxvalue]();
? ? //重點(diǎn)錯(cuò)誤
? ? //for(int i=0; i<=m; i++)是錯(cuò)的
? ? for(int i=1; i<=m; i++) ?dp[i] = maxvalue;
? ? int i,j,k;
? ? for(i=0; i<n; i++)//硬幣面值的種數(shù)
? ? {
? ? ? ? for(j=1; j<=coincount[i]; j++)//硬幣的面值的個(gè)數(shù)
? ? ? ? {
? ? ? ? ? ? for(k=m; k>=coin[i]; k--) //動(dòng)態(tài)遷移方程為
? ? ? ? ? ? ? ? dp[k] = mymin(dp[k - coin[i]] + 1, dp[k]);
? ? ? ? }
? ? }
? ??
? ? if(dp[m] == maxvalue)
? ? ? ? cout << -1 << endl;
? ? else cout << dp[m] << endl;
? ? return 0;
}

??石子合并問題

?題面：

在一個(gè)圓形操場(chǎng)的四周擺放著 n 堆石子?，F(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的 2 堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。試設(shè)計(jì)一個(gè)算法，計(jì)算出將 n 堆石子合并成一堆的最小得分和最大得分。

算法設(shè)計(jì)：對(duì)于給定 n 堆石子,計(jì)算合并成一堆的最小得分和最大得分

【輸入形式】
輸入數(shù)據(jù)：第 1 行是正整數(shù) n，1≤n≤100，表示有 n 堆石子。
第二行有 n 個(gè)數(shù)，分別表示每堆石子的個(gè)數(shù)。
【輸出形式】
將計(jì)算結(jié)果輸出：第 1 行中的數(shù)是最小得分；第 2 行中的數(shù)是最大得分。

【樣例輸入】
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]; ? ?//已保存的狀態(tài)不必搜索?
? ? if(L==R) ? ?return f1[L][R]=0; ? ?//L==R時(shí)返回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; ? ? ? ? ? ?//記錄狀態(tài)?
}
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; ? ? ? ? ? ? ? ? ? ? ? ?//初始值設(shè)為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]; ? ? ? ? ? ? ? ?//因?yàn)槭黔h(huán)所以保存為長(zhǎng)度為2n的鏈以保證不會(huì)漏解?
? ? }
? ? 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;
}

??序關(guān)系計(jì)數(shù)問題

?題面：

用關(guān)系“<”和“=”將 3 個(gè)數(shù) A、B 和 C 依序排列時(shí)有 13 種不同的序關(guān)系：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 個(gè)數(shù)（1 ≤ n ≤50）依序排列時(shí)有多少種序關(guān)系。

算法設(shè)計(jì)：計(jì)算出將 n 個(gè)數(shù)（1 ≤ n ≤50）依序排列時(shí)有多少種序關(guān)系

【輸入形式】
輸入數(shù)據(jù)：輸入數(shù)據(jù)有多行，每行提供一個(gè)數(shù)n 。
【輸出形式】
將找到的序關(guān)系數(shù)輸出：一行一個(gè)。

【樣例輸入】
3
5
【樣例輸出】
13
541

?代碼&注釋：

/*
--------------------------------------
-----Problem: 8923.序關(guān)系計(jì)數(shù)問題-----
---------------Author-----------------
---------------XZITXX----------------
--------------------------------------
*/
#include <bits/stdc++.h>
#define MAX_N 51
using namespace std;
?
__int64 dp[MAX_N][MAX_N];?? ?//dp[i][j]：i個(gè)數(shù)，有j個(gè)‘<’鏈接，共有多少種情況
?
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;
}

??汽車加油行駛問題

?題面：

給定一個(gè)N*N 的方形網(wǎng)格，設(shè)其左上角為起點(diǎn)，坐標(biāo)為（1,1），X 軸向右為正，Y 軸向下為正，每個(gè)方格邊長(zhǎng)為1。一輛汽車從起點(diǎn)出發(fā)駛向右下角終點(diǎn)，其坐標(biāo)為（N,N）。在若干個(gè)網(wǎng)格交叉點(diǎn)處，設(shè)置了油庫，可供汽車在行駛途中加油。汽車在行駛過程中應(yīng)遵守
如下規(guī)則：（1）汽車只能沿網(wǎng)格邊行駛，裝滿油后能行駛K 條網(wǎng)格邊。出發(fā)時(shí)汽車已裝滿油，在起點(diǎn)與終點(diǎn)處不設(shè)油庫。（2）當(dāng)汽車行駛經(jīng)過一條網(wǎng)格邊時(shí)，若其 X 坐標(biāo)或 Y 坐標(biāo)減小，則應(yīng)付費(fèi)用B，否則免付費(fèi)用。（3）汽車在行駛過程中遇油庫則應(yīng)加滿油并付加油費(fèi)用A。（4）在需要時(shí)可在網(wǎng)格點(diǎn)處增設(shè)油庫，并付增設(shè)油庫費(fèi)用C（不含加油費(fèi)用A）。（5）(1)～(4)中的各數(shù)N、K、A、B、C均為正整數(shù)。

算法設(shè)計(jì)：求汽車從起點(diǎn)出發(fā)到達(dá)終點(diǎn)的一條所付費(fèi)用最少的行駛路線

【輸入形式】
輸入數(shù)據(jù)：
第一行是N，K，A，B，C的值，2 ≤ N ≤ 100，2 ≤ K ≤ 10。第二行起是一個(gè)N*N 的0-1方陣，每行N 個(gè)值，至N+1行結(jié)束。方陣的第i行第j 列處的值為1 表示在網(wǎng)格交叉點(diǎn)（i，j）處設(shè)置了一個(gè)油庫，為0 時(shí)表示未設(shè)油庫。各行相鄰的2 個(gè)數(shù)以空格分隔。
【輸出形式】
將找到的最優(yōu)行駛路線所需的費(fèi)用，即最小費(fèi)用輸出：第1行中的數(shù)是最小費(fèi)用值。

【樣例輸入】
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;
}

??租用游艇問題

?題面：

長(zhǎng)江游艇俱樂部在長(zhǎng)江上設(shè)置了 n 個(gè)游艇出租站 1，2，…，n。游客可在這些游艇出租站租用游艇，并在下游的任何一個(gè)游艇出租站歸還游艇。游艇出租站 i 到游艇出租站 j 之間的租金為 r(i,j),1≤i<j≤n。試設(shè)計(jì)一個(gè)算法，計(jì)算出從游艇出租站 1 到游艇出租站 n 所需的最少租金。

算法設(shè)計(jì)：對(duì)于給定的游艇出租站 i 到游艇出租站 j 之間的租金為 r(i,j),1≤i<j≤n，計(jì)算從游艇出租站 1 到游艇出租站 n 所需的最少租金

【輸入形式】
輸入數(shù)據(jù)：第 1 行中有 1 個(gè)正整數(shù) n（n<=200），表示有 n個(gè)游艇出租站。接下來的 n-1 行是 r(i,j),1≤i<j≤n。
【輸出形式】
將計(jì)算出的從游艇出租站 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個(gè)游艇出租站所需的最少租金

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;
}

??紅黑樹的紅色內(nèi)結(jié)點(diǎn)問題

?題面：

紅黑樹是一類特殊的二叉搜索樹，其中每個(gè)結(jié)點(diǎn)被“染成”紅色或黑色。若將二叉搜索樹結(jié)點(diǎn)中的空指針看作是指向一個(gè)空結(jié)點(diǎn)，則稱這類空結(jié)點(diǎn)為二叉搜索樹的前端結(jié)點(diǎn)。并規(guī)定所有前端結(jié)點(diǎn)的高度為-1。

一棵紅黑樹是滿足下面“紅黑性質(zhì)”染色二叉搜索樹：
(1)每個(gè)結(jié)點(diǎn)被染成紅色或黑色；
(2)每個(gè)前端結(jié)點(diǎn)為黑色結(jié)點(diǎn)；
(3)任一紅結(jié)點(diǎn)的兒子結(jié)點(diǎn)均為黑結(jié)點(diǎn)；
(4)在從任一結(jié)點(diǎn)到其子孫前端結(jié)點(diǎn)的所有路徑上具有相同的黑結(jié)點(diǎn)數(shù)。

從紅黑樹中任一結(jié)點(diǎn) x 出發(fā)(不包括結(jié)點(diǎn) x)，到達(dá)一個(gè)前端結(jié)點(diǎn)的任意一條路徑上的黑結(jié)點(diǎn)個(gè)數(shù)稱為結(jié)點(diǎn) x 的黑高度，記作 bh(x)。紅黑樹的黑高度定義為其根結(jié)點(diǎn)的黑高度。圖示的二叉搜索樹是一棵紅黑樹。標(biāo)在結(jié)點(diǎn)旁邊的數(shù)字是相應(yīng)結(jié)點(diǎn)的黑高度。

算法設(shè)計(jì)：給定正整數(shù) n，試設(shè)計(jì)一個(gè)算法，計(jì)算出在所有含有 n 個(gè)結(jié)點(diǎn)的紅黑樹中，紅色內(nèi)結(jié)點(diǎn)個(gè)數(shù)的最小值和最大值

【輸入形式】
輸入數(shù)據(jù)：第一行是正整數(shù) n，1<n<5000。
【輸出形式】
將紅色內(nèi)結(jié)點(diǎn)個(gè)數(shù)的最小值和最大值輸出：第 1 行是最小值，第 2行是最大值。

【樣例輸入】
8
【樣例輸出】
1
4

?代碼&注釋：

/*
--------------------------------------
-----8830. 紅黑樹的紅色內(nèi)結(jié)點(diǎn)問題-----
------------------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;
}

??編輯距離問題

?題面：

設(shè) A 和 B 是 2 個(gè)字符串。要用最少的字符操作將字符串 A 轉(zhuǎn)換為字符串 B。這里所說的字符操作包括
(1)刪除一個(gè)字符；
(2)插入一個(gè)字符；
(3)將一個(gè)字符改為另一個(gè)字符。

將字符串 A 變換為字符串 B 所用的最少字符操作數(shù)稱為字符串 A 到 B 的編輯距離，記為d(A,B)。試設(shè)計(jì)一個(gè)有效算法，對(duì)任給的2個(gè)字符串A和B，計(jì)算出它們的編輯距離d(A,B)。

算法設(shè)計(jì)：對(duì)于給定的字符串 A 和字符串 B，計(jì)算其編輯距離 d(A,B)

【輸入形式】
輸入數(shù)據(jù)：第一行是字符串 A，文件的第二行是字符串 B。
【輸出形式】
將編輯距離 d(A,B)輸出到第 1 行中。

【樣例輸入】
fxpimu
xwrs
【樣例輸出】
5

?代碼&注釋：

/*
--------------------------------------
------------8829. 編輯距離問題--------
------------------Author--------------
------------------XZITXX--------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
int d[2005][2005];

/*
輸入的兩個(gè)字符數(shù)組為a[], b[]，從下標(biāo)為0開始初始化
長(zhǎng)度分別為length_a, length_b?
數(shù)組d[m][n]存放從a[1:m] 變?yōu)?b[1:n]所需要的最少操作
遞歸公式：
?? ?d[i][j] = 0, ? ?i=0或j=0 時(shí)(即數(shù)組的第一行和第一列均為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]
最優(yōu)值：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);
}?

??雙調(diào)旅行售貨員問題

?題面：

歐氏旅行售貨員問題是對(duì)給定的平面上n 個(gè)點(diǎn)確定一條連接這n 個(gè)點(diǎn)的長(zhǎng)度最短的哈密頓回路。由于歐氏距離滿足三角不等式，所以歐氏旅行售貨員問題是一個(gè)特殊的具有三角不等式性質(zhì)的旅行售貨員問題。它仍是一個(gè)NP完全問題。最短雙調(diào)TSP回路是歐氏旅行售貨員問題的特殊情況。平面上n 個(gè)點(diǎn)的雙調(diào)TSP 回路是從最左點(diǎn)開始，嚴(yán)格地由左至右直到最右點(diǎn)，然后嚴(yán)格地由右至左直至最左點(diǎn)，且連接每一個(gè)點(diǎn)恰好一次的一條閉合回路。

算法設(shè)計(jì)：給定平面上 n 個(gè)點(diǎn)，計(jì)算這 n 個(gè)點(diǎn)的最短雙調(diào)TSP回路

【輸入形式】
輸入數(shù)據(jù)：第1 行有1 個(gè)正整數(shù)n，表示給定的平面上的點(diǎn)數(shù)。接下來的n行中，每行2 個(gè)實(shí)數(shù)，分別表示點(diǎn)的x坐標(biāo)和y坐標(biāo)。
【輸出形式】
將計(jì)算的最短雙調(diào)TSP回路的長(zhǎng)度（保留2 位小數(shù)）輸出。

【樣例輸入】
7
0 6
1 0
2 3
5 4
6 1
7 5
8 2
【樣例輸出】
25.58

?代碼&注釋：

/*
--------------------------------------
---Problem: 8908.雙調(diào)旅行售貨員問題---
-----------------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個(gè)點(diǎn)與第j個(gè)點(diǎn)的距離?
? ? for(int i=1; i<=n; i++)//d[i][j](i>j)表示從第i個(gè)點(diǎn)到第一個(gè)點(diǎn)再到第j個(gè)點(diǎn)距離?
? ? ? ? cin>>x[i]>>y[i];
? ??
? ? for(int i=1; i<=n; i++) {//按x坐標(biāo)排序?
? ? ? ? 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]);//計(jì)算兩點(diǎn)間距離?
? ? ? ??
? ??
? ? 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個(gè)點(diǎn)到第一個(gè)點(diǎn)再回到第i個(gè)點(diǎn)的距離，先初始化為一個(gè)很大的值?
? ? ? ? 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}上的乘法表如下

依此乘法表，對(duì)任一定義于Σ上的字符串，適當(dāng)加括號(hào)后得到一個(gè)表達(dá)式。例如，對(duì)于字符串 x=bbbba，它的一個(gè)加括號(hào)表達(dá)式為(b(bb))(ba)。依乘法表，該表達(dá)式的值為 a。試設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，對(duì)任一定義于Σ上的字符串blob.png，計(jì)算有多少種不同的加括號(hào)方式，使由 x 導(dǎo)出的加括號(hào)表達(dá)式的值為 a。

算法設(shè)計(jì)：對(duì)于給定的字符串 blob.png，計(jì)算有多少種不同的加括號(hào)方式，使由 x 導(dǎo)出的加括號(hào)表達(dá)式的值為 a

【輸入形式】
輸入數(shù)據(jù)：第 1 行中給出一個(gè)字符串。
【輸出形式】
將計(jì)算結(jié)果輸出：第 1 行中的數(shù)是計(jì)算出的加括號(hào)方式數(shù)。

【樣例輸入】
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;//字符串的長(zhǎng)度
? ? 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++)
? ? ? ? {//接著從長(zhǎng)度為 2 的子字符串計(jì)算，直至計(jì)算好整串 str
? ? ? ? ? ? for(int i=1; i<=len-r+1; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int j = i+r-1;//計(jì)算str[i:j]
? ? ? ? ? ? ? ? for (int k=i; k<=j; k++)
? ? ? ? ? ? ? ? {//根據(jù)題目中的表，計(jì)算加括號(hào)法
? ? ? ? ? ? ? ? ? ? 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;
}

??圈乘運(yùn)算問題

?題面：

關(guān)于整數(shù)的 2 元圈乘運(yùn)算?定義為（X?Y）=10 進(jìn)制整數(shù) X 的各位數(shù)字之和 * 10 進(jìn)制整數(shù) Y 的最大數(shù)字+Y 的最小數(shù)字。例如,（9?30）=9*3+0=27。對(duì)于給定的 10 進(jìn)制整數(shù) X 和 K，由 X 和?運(yùn)算可以組成各種不同的表達(dá)式。試設(shè)計(jì)一個(gè)算法，計(jì)算出由 X 和?運(yùn)算組成的值為 K 的表達(dá)式最少需用多少個(gè)?運(yùn)算。

算法設(shè)計(jì)：給定 10 進(jìn)制整數(shù) X 和 K (1≤X,K≤1020) ，計(jì)算由 X 和?運(yùn)算組成的值為 K 的表達(dá)式最少需用多少個(gè)?運(yùn)算

【輸入形式】
輸入數(shù)據(jù)：每一行有 2 個(gè) 10 進(jìn)制整數(shù) X 和 K。最后一行是 0 0（以0 0結(jié)束）。
【輸出形式】
將找到的最少?運(yùn)算個(gè)數(shù)輸出。

【樣例輸入】
3 12
0 0
【樣例輸出】
1

這題TLE了

?代碼&注釋：

/*
--------------------------------------
-----------8911. 圈乘運(yùn)算問題---------
-----------------Author---------------
-----------------XZITXX---------------
--------------------------------------
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX=81*30+9,MIN=-1;

int NumLen(int x){//統(tǒng)計(jì)位數(shù)
?? ?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;//存放最小圈乘次數(shù)
?? ?a[1] = num;//存放各位數(shù)之和
?? ?a[2] = min;//存放最小的數(shù)
?? ?a[3] = max;//存放最大的數(shù)
}
?
int main()
{
?? ?int x,k;
?? ?while(~scanf("%d%d",&x,&k)&&x!=0&&k!=0)
?? ?{
?? ??? ?int n = NumLen(x);//表示x的位數(shù)
?? ? ? ?int m = 81*n+9;//b最小可以2為數(shù)組合，最大為9，最小為9.所以（x的各位數(shù)相加）*9+9；x的各位數(shù)相加最大為9*n；
?? ? ? ?if(m<177){//因?yàn)閥可能是2位數(shù)，導(dǎo)致1位數(shù)的x圈乘后的結(jié)果為2位數(shù)
?? ??? ? ? ?m = 177;
?? ? ? ?}
?? ? ? ?if (k>m){//若k大于x的最大圈乘數(shù)則退出
?? ??? ? ? ?return -1;
?? ? ? ?}
?? ? ? ?int** r = new int*[m+2];//建立二維數(shù)組
?? ? ? ?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寫到數(shù)組的最后
?? ? ? ?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];//計(jì)算圈乘結(jié)果
?? ??? ??? ??? ??? ??? ? ? ?if (r[tend][0]>r[i][0]+r[j][0]+1){//與原來的圈乘生產(chǎn)該數(shù)的次數(shù)對(duì)比找最小
?? ??? ??? ??? ??? ??? ??? ? ? ?flag = 1;//若有變化則更新x的尋值
?? ??? ??? ??? ??? ??? ??? ? ? ?r[tend][0] = r[i][0] + r[j][0] + 1; //r[i][0]為得到x的圈乘次數(shù),r[j][0]位得到y(tǒng)的圈乘次數(shù)
?? ??? ??? ??? ??? ??? ? ? ?}//endif
?? ??? ??? ??? ??? ? ? ?}//endif
?? ??? ??? ??? ? ? ?}
?? ??? ??? ? ? ?}//endif
?? ??? ? ? ?}
?? ? ? ?}
?? ? ? ?cout << r[k][0] << endl;
?? ?}
?? ?return 0;
}

??【專題】回溯與分支限界

??最小長(zhǎng)度電路板排列問題

?題面：

最小長(zhǎng)度電路板排列問題是大規(guī)模電子系統(tǒng)設(shè)計(jì)中提出的實(shí)際問題。該問題的提法是， 將 n 塊電路板以最佳排列方案插入帶有 n 個(gè)插槽的機(jī)箱中。n 塊電路板的不同的排列方式對(duì) 應(yīng)于不同的電路板插入方案。 設(shè) B={1，2，…，n }是 n 塊電路板的集合。集合 L={ N1， N2 ，…， N m }是 n 塊電路 板的 m 個(gè)連接塊。其中每個(gè)連接塊 Ni 是 B 的一個(gè)子集，且 Ni 中的電路板用同一根導(dǎo)線連 接在一起。 例如，設(shè) n=8，m=5。給定 n 塊電路板及其 m 個(gè)連接塊如下： 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 塊電路板的一個(gè)可能的排列如圖所示

在最小長(zhǎng)度電路板排列問題中，連接塊的長(zhǎng)度是指該連接塊中第 1 塊電路板到最后 1 塊電路板之間的距離。例如在圖示的電路板排列中，連接塊 N4 的第 1 塊電路板在插槽 3 中， 它的最后 1 塊電路板在插槽 6 中，因此 N4 的長(zhǎng)度為 3。同理 N2 的長(zhǎng)度為 2。圖中連接塊最 大長(zhǎng)度為 3。試設(shè)計(jì)一個(gè)分支限界法找出所給 n 個(gè)電路板的最佳排列，使得 m 個(gè)連接塊中最 大長(zhǎng)度達(dá)到最小。
對(duì)于給定的電路板連接塊，設(shè)計(jì)一個(gè)隊(duì)列式分支限界法，找出所給 n 個(gè)電路板的最佳排 列，使得 m 個(gè)連接塊中最大長(zhǎng)度達(dá)到最小。??

【輸入形式】
第一行有 2 個(gè)正整數(shù) n 和 m (1≤m,n≤20)。接下來的 n 行中，每行有 m 個(gè)數(shù)。第 k 行的第 j 個(gè)數(shù)為 0 表示電路板 k 不在連接塊 j 中，1 表示電路板 k 在連接塊 j 中。?
【輸出形式】
將計(jì)算出的電路板排列最小長(zhǎng)度及其最佳排列輸出。
文件的第 1 行是 最小長(zhǎng)度；接下來的 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

?代碼&注釋：

/*最小長(zhǎng)度電路板排列問題*/
#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 *));//申請(qǐng)一組一維指針空間。
? ??
?? ?for(int i=0; i<n; i++)
? ? ? ? arr[i] = (int *)malloc(m*sizeof(int)); //對(duì)于每個(gè)一維指針，申請(qǐng)一行數(shù)據(jù)的空間。
? ??
?? ?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;
}

??圓排列問題

?題面：

算法設(shè)計(jì)：對(duì)于給定的 n 個(gè)圓，設(shè)計(jì)一個(gè)優(yōu)先隊(duì)列式分支限界法，計(jì)算 n 個(gè)圓的最佳排列方案，使其長(zhǎng)度達(dá)到最小

【輸入形式】
輸入數(shù)據(jù)。第一行有 1 個(gè)正整數(shù) n (1≤n≤20)。接下來的 1 行有 n個(gè)數(shù)，表示 n 個(gè)圓的半徑。
【輸出形式】
將計(jì)算出的最小圓排列的長(zhǎng)度輸出。

【樣例輸入】
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];//分別為最小圓排列長(zhǎng)度，每個(gè)圓心橫坐標(biāo)，每個(gè)圓半徑
double bestr[MAX_SIZE];//最小圓排列的半徑順序

//計(jì)算圓心橫坐標(biāo)
double center(int t)//得到每個(gè)圓的圓心坐標(biāo)
{
?? ?double temp = 0;
?? ?for (int j=1; j<t; ++j)//因?yàn)槟繕?biāo)圓有可能與排在它之前的任一圓相切，故需一一判斷
?? ?{
?? ??? ?double xvalue = x[j] + 2.0*sqrt(r[t]*r[j]);
?? ??? ?temp = max(xvalue, temp);
?? ?}
?? ?return temp;
}

//計(jì)算圓排列長(zhǎng)度
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();//計(jì)算圓排列長(zhǎng)度
?? ??? ?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個(gè)圓
?? ??? ?}
?? ??? ?swap(r[t], r[j]);//恢復(fù)狀態(tài)
?? ?}
}

int main()
{
?? ?cin >> N;
?? ?N++;
?? ?for(int i=1; i<N; i++)?? ?cin >> r[i];
?? ?backtrack(1);
?? ?cout << minlen << endl;
?? ?return 0;
}

??推箱子問題

?題面：

碼頭倉庫是劃分為 n×m 個(gè)格子的矩形陣列。有公共邊的格子是相鄰格子。當(dāng)前倉庫中有的格子是空閑的；有的格子則已經(jīng)堆放了沉重的貨物。由于堆放的貨物很重，單憑倉庫管理員的力量是無法移動(dòng)的。倉庫管理員有一項(xiàng)任務(wù)，要將一個(gè)小箱子推到指定的格子上去。管理員可以在倉庫中移動(dòng)，但不能跨過已經(jīng)堆放了貨物的格子。管理員站在與箱子相對(duì)的空閑格子上時(shí)，可以做一次推動(dòng)，把箱子推到另一相鄰的空閑格子。推箱時(shí)只能向管理員的對(duì)面方向推。由于要推動(dòng)的箱子很重，倉庫管理員想盡量減少推箱子的次數(shù)。
對(duì)于給定的倉庫布局，以及倉庫管理員在倉庫中的位置和箱子的開始位置和目標(biāo)位置，設(shè)計(jì)一個(gè)解推箱子問題的分支限界法，計(jì)算出倉庫管理員將箱子從開始位置推到目標(biāo)位置所需的最少推動(dòng)次數(shù)。

【輸入形式】
輸入數(shù)據(jù)的第1 行有2個(gè)正整數(shù)n和m（1<=n,m<=100），表示倉庫是n×m個(gè)格子的矩形陣列。接下來有n行，每行有m個(gè)字符，表示格子的狀態(tài)。
S 表示格子上放了不可移動(dòng)的沉重貨物；
w 表示格子空閑；
M 表示倉庫管理員的初始位置；
P 表示箱子的初始位置；
K 表示箱子的目標(biāo)位置。
【輸出形式】
將計(jì)算出的最少推動(dòng)次數(shù)輸出。如果倉庫管理員無法將箱子從開始位置推到目標(biāo)位置則輸出“No solution！”

【樣例輸入】
10 12
SSSSSSSSSSSS
SwwwwwwwSSSS
SwSSSSwwSSSS
SwSSSSwwSKSS
SwSSSSwwSwSS
SwwwwwPwwwww
SSSSSSSwSwSw
SSSSSSMwSwww
SSSSSSSSSSSS
SSSSSSSSSSSS
【樣例輸出】
7

?詳細(xì)思路過程&代碼&注釋&優(yōu)化：

?優(yōu)化后代碼：

#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) { // 求十進(jìn)制數(shù)的二進(jìn)制中1的個(gè)數(shù)
? ? 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;?
}

算法設(shè)計(jì)與分析之 “貪心” 經(jīng)典習(xí)題總結(jié)&AC代碼_夏旭的博客-CSDN博客

算法設(shè)計(jì)與分析之 “遞歸與分治” 經(jīng)典習(xí)題總結(jié)&AC代碼_夏旭的博客-CSDN博客

算法設(shè)計(jì)與分析之 “動(dòng)態(tài)規(guī)劃” 經(jīng)典習(xí)題總結(jié)&AC代碼_夏旭的博客-CSDN博客

算法設(shè)計(jì)與分析之 “回溯與分支限界法” 經(jīng)典習(xí)題總結(jié)&AC代碼_夏旭的博客-CSDN博客文章來源地址http://www.zghlxwxcb.cn/news/detail-492447.html

到了這里，關(guān)于【算法設(shè)計(jì)與分析】經(jīng)典常考三十三道例題&AC代碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！