算法考试题

分治法课堂案例

第1关：二分搜索技术

任务描述

本关任务：给定一组有序整数，用二分查找技术查找X是否在序列中，在则输出Yes，不在则输出No。输入格式：三行，第一行一个整数n，第二行n个正整数，且有序；第三行是要查找的X 输出格式：X在序列中输出下标（0开始），不在输出-1

编程要求

根据提示，在右侧编辑器补充代码。

测试说明

平台会对你编写的代码进行测试：

测试输入： 10 11 21 22 32 41 51 52 62 71 82 22 预期输出： 2

开始你的任务吧，祝你成功！

答案：

#include<iostream>
using namespace std; 
#include<stdio.h>
const int N = 10000; 
int BSearch(int a[], int l, int r,int x)
{
/***********Begin***************/
int m=(l+r)/2;
while(l<=r)
{
  if(a[m]>x)
  {
    r=r-1;
    m=(l+r)/2;
  }
  else if(a[m]<x)
  {
    l=l+1;
    m=(l+r)/2;
  }
  else
  {
  
    break;
  }

}
if(l<=r)
return m;
else
return -1;



/***********End***************/
}
int main()
{
  int n,x,a[N];
  cin>>n;  

  for(int i = 0; i < n; i++)
     cin>>a[i];
  cin>>x;  
  cout<<BSearch(a,0,n-1,x);
  return 0;


}

第2关：棋盘覆盖问题

任务描述

在一个

解释

2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

例如:4×4的棋盘的一种覆盖方法为：

编写函数，输出给定k的一种棋盘覆盖。

编程要求

根据提示，在右侧编辑器补充代码。

输入格式

输入为三个正整数： size dr dc 其中(size=2k,0≤k≤5)，(dr,dc)是特殊方格的位置,且0≤dr,dc≤size−1

输出格式

输出棋盘覆盖方案，特殊方格处输出-1，其他位置处同一编号的L形骨牌用同一个数字表示，数字占宽4格，右对齐。

输入输出示例

测试输入：8 3 2 预期输出：

2 2 3 3 7 7 8 8
2 1 1 3 7 6 6 8
4 1 5 5 9 9 6 10
4 4 -1 5 0 9 10 10
12 12 13 0 0 17 18 18
12 11 13 13 17 17 16 18
14 11 11 15 19 16 16 20
14 14 15 15 19 19 20 20

开始你的任务吧，祝你成功！

答案：

#include<iostream>
#include<iomanip>
# define SIZE 32
using namespace std;

int tile = 0;
int Board[SIZE][SIZE];
//棋盘以(tr,tc)为左上角，以size为边长，特殊方格位置在(dr,dc)，ChessBoard函数用分治法
//完成它四个子棋盘覆盖
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
/************Begin**************/
if(size==1) return ;
int t=tile++;
int s=size/2;
if(dr<tr+s&&dc<tc+s)
    ChessBoard(tr,tc,dr,dc,s);
else{
  Board[tr+s-1][tc+s-1]=t;
  ChessBoard(tr,tc,tr+s-1,tc+s-1,s);
}
if(dr<tr+s&&dc>=tc+s)
    ChessBoard(tr,tc+s,dr,dc,s);
else{
  Board[tr+s-1][tc+s]=t;
  ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
}
if(dr>=tr+s&&dc<tc+s)
    ChessBoard(tr+s,tc,dr,dc,s);
else{
  Board[tr+s][tc+s-1]=t;
  ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
}
if(dr>=tr+s&&dc>=tc+s)
    ChessBoard(tr+s,tc+s,dr,dc,s);
else{
  Board[tr+s][tc+s]=t;
  ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
/************End**************/

}
int main()
{
    /************Begin**************/
    int size,dr,dc;
    cin>>size>>dr>>dc;
    Board[dr][dc]=-1;
    ChessBoard(0,0,dr,dc,size);
    /************End**************/
    for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++)
			cout << setw(4) << Board[i][j];
		cout << endl;
    }
return 0;
}

第3关：合并排序

任务描述

本关任务：用合并排序方法对数组a元素排序。输入：两行，第一行是正整数n,第二行是n个正整数输出：排好序的一行正整数

编程要求

根据提示，在右侧编辑器补充代码。

测试说明

平台会对你编写的代码进行测试：

测试输入： 8 4 5 3 2 9 7 1 8 预期输出： 1 2 3 4 5 7 8 9

开始你的任务吧，祝你成功！

答案：

#include<iostream> 
using namespace std;  
const int N = 1000;
/*******Begin***********/
void Merge(int a[],int b[],int l,int i,int r)
{
    int j=l,k=i+1,m=l;
 while(j<=i&&k<=r)
 {
     if(a[j]>a[k])
     {
         b[m]=a[k];
         k++;
         m++;
     }
     else
     {
         b[m]=a[j];
         j++;
         m++;
     }
 }
 while(j<=i)
 {
     b[m]=a[j];
     m++;
     j++;
 }
 while(k<=r)
 {
     b[m]=a[k];
     m++;
     k++;
 }
 for(int u=l;u<=r;u++)
 a[u]=b[u];
}
void MergeSort(int a[],int b[],int l,int r )
{
    if(l<r)
    {
        int i=(l+r)/2;
        MergeSort(a,b,l,i);
        MergeSort(a,b,i+1,r);
        Merge(a,b,l,i,r);
       
    }
}






/*******End***********/


int main( )
{
    int n,a[N],b[N]; 
    cin>>n; 
    for(int i = 0 ; i < n; i ++)cin>>a[i]; 
    MergeSort(a,b,0,n-1);
    for(int i = 0 ; i < n - 1; i ++)cout<<a[i]<<" "; 
    cout<<a[n-1];
    return 0;

}

第4关：快速排序

任务描述

本关任务：用快速排序方法对数组a元素排序。输入：两行，第一行是正整数n,第二行是n个正整数输出：排好序的一行正整数

编程要求

根据提示，在右侧编辑器补充代码。

测试说明

平台会对你编写的代码进行测试：

测试输入： 8 4 5 3 2 9 7 1 8 预期输出： 1 2 3 4 5 7 8 9

开始你的任务吧，祝你成功！

答案：

#include<iostream> 
using namespace std;    
const int N = 1000;  
  
// 快速排序的划分函数  
int Partition(int a[], int left, int right) {  
    int pivot = a[right]; // 选择最右边的元素作为基准  
    int i = left - 1; // 指向小于基准的元素的最后一个位置  
    for (int j = left; j < right; j++) {  
        if (a[j] <= pivot) {  
            i++;  
            swap(a[i], a[j]); // 交换元素，使得小于基准的元素在左边  
        }  
    }  
    swap(a[i + 1], a[right]); // 将基准元素放到最终位置  
    return i + 1;  
}  
  
// 快速排序的递归函数  
void QuickSort(int a[], int left, int right) {  
    if (left < right) {  
        int pivotIndex = Partition(a, left, right);  
        QuickSort(a, left, pivotIndex - 1); // 递归处理左半部分  
        QuickSort(a, pivotIndex + 1, right); // 递归处理右半部分  
    }  
}  
  
/**************Begin*********/  
  
// 在这里不需要额外添加代码，因为上面的QuickSort函数已经足够用于排序  
  
/**************End*********/  
  
int main() {  
    int n, a[N];  
    cin >> n;  
    for (int i = 0; i < n; i++) cin >> a[i];  
    QuickSort(a, 0, n - 1); // 调用快速排序函数  
    for (int i = 0; i < n - 1; i++) cout << a[i] << " ";  
    cout << a[n - 1];  
    return 0;  
}

第5关：线性时间选择问题

任务描述

给定线性无序数组n个元素和一个正整数k,1≤k≤n,要求在线性时间找到这n个元素的第k小。

编程要求

完成一个冒泡排序函数:

void BubbleSort(Type a[],int p,int r)

完成根据基准元素x进行划分的函数:

int Partition(int a[],int p,int r,Type x)

完成线性时间选择数组a[p]~a[r]的第k小函数:

int Select(int a[],int p,int r,int k)

数组元素个数小于等于75时，直接用冒泡排序，返回第k小
数组元素个数大于等于75时，调用Select函数，返回第k小

测试说明

函数中数组的元素是整型，返回值也是整型。
输入的数组元素是整型，且不重复。主函数如下：
1. #include<iostream>
2. using namespace std;
3. int main()
4. {
5. int a[1000]={0},n,k;
6. cin>>n;
7. for(int i = 0; i < n; i ++)
8. cin>>a[i];
9. cin>>k;
10. cout<<Select(a,0,n-1,k)<<endl;
11. return 0;
12. }
直接完成要求函数即可，输入输出由隐藏主函数完成。

开始你的任务吧，祝你成功！

答案：

void Swap(int &a,int &b)
{//交换函数
	 /*********begin************/
    int c;
	c = a;
	a = b;
	b = c;

    /*********end************/
}


int Partition(int a[],int p,int r,int x)
{//以x为基准划分函数
	 /*********begin************/


    /*********end************/
}

void BubbleSort(int a[],int p,int r)
{//冒泡排序
    
    /*********begin************/
    int i,j,temp;
    for(i=0;i<r;i++){
        for(j=0;j<r-i;j++){
            if(a[j]>a[j+1]){
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    /*********end************/
	
}
int Select(int a[],int p,int r,int k)
{
    /*********begin************/
    if(k<=75){
        BubbleSort(a,p,r);
        return a[p+k-1];
    }

    



    /*********end************/
}

第6关：一维空间最短距离

任务描述

本关任务：S中的n个点为x轴上的n个实数。最接近点对即为这n个实数中相差最小的两个实数。给定n个实数，用分治法求最接近点对的距离。例如： 11个点： 1.1 4.5 3.2 2.7 7.8 9.1 5.5 1.9 7.4 9.9 2.2 最接近点对距离是：0.3

编程要求

根据提示，在右侧编辑器补充代码。

测试说明

输入格式：两行，第一行正整数N,第二行n个实数输出格式：这n个实数的最接近点对距离

测试输入： 11 1.1 4.5 3.2 2.7 7.8 9.1 5.5 1.9 7.4 9.9 2.2 预期输出： 0.3

开始你的任务吧，祝你成功！

答案：

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <cmath>  
using namespace std;  
  
const double MAX = 9999.99;  
const int N = 1000;  
  
// 用于存储点的结构体  
struct Point {  
    double x;  
    int index; // 存储原始数组中的索引，以便找到对应的点  
};  
  
// 辅助函数：比较两个点的x坐标  
bool cmpX(const Point& a, const Point& b) {  
    return a.x < b.x;  
}  
  
// 辅助函数：比较两个点的y坐标  
bool cmpY(const Point& a, const Point& b) {  
    return a.x - a.index < b.x - b.index;  
}  
  
// 计算两点之间的距离  
double distance(const Point& a, const Point& b) {  
    return fabs(a.x - b.x);  
}  
  
// 辅助函数：寻找条带内的最小距离  
double stripClosest(const vector<Point>& strip, int size) {  
    double minDist = MAX;  
    vector<Point> sortedY(strip.begin(), strip.begin() + size);  
    sort(sortedY.begin(), sortedY.end(), cmpY);  
  
    for (int i = 0; i < size; ++i) {  
        for (int j = i + 1; j < size && sortedY[j].x - sortedY[i].x < minDist; ++j) {  
            double d = distance(sortedY[i], sortedY[j]);  
            if (d < minDist) {  
                minDist = d;  
            }  
        }  
    }  
    return minDist;  
}  
  
// 递归函数：计算最接近点对距离  
double Cpair(const vector<Point>& points, int left, int right, double& d) {  
    if (left == right) {  
        return d;  
    }  
    if (left + 1 == right) {  
        d = min(d, distance(points[left], points[right]));  
        return d;  
    }  
  
    int mid = left + (right - left) / 2;  
    double dl = Cpair(points, left, mid, d);  
    double dr = Cpair(points, mid, right, d);  
    d = min(d, min(dl, dr));  
  
    // 合并左右两侧的结果  
    vector<Point> strip;  
    for (int i = left; i <= right; ++i) {  
        if (fabs(points[i].x - points[mid].x) < d) {  
            strip.push_back(points[i]);  
        }  
    }  
    d = min(d, stripClosest(strip, int(strip.size())));  
    return d;  
}  
  
// 主函数：调用递归函数，并初始化相关参数  
double Cpair1(double a[], int n, double& d) {  
    vector<Point> points(n);  
    for (int i = 0; i < n; ++i) {  
        points[i].x = a[i];  
        points[i].index = i; // 存储原始数组的索引  
    }  
    sort(points.begin(), points.end(), cmpX);  
    return Cpair(points, 0, n - 1, d);  
}  
  
int main() {  
    int n;  
    double a[N];  
    double d = MAX;  
    cin >> n;  
    for (int i = 0; i < n; i++) {  
        cin >> a[i];  
    }  
  
    Cpair1(a, n, d);  
    cout << d << endl;  
  
    return 0;  
}

第7关：众数问题

任务描述

给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中最大的元素称为众数。给定一个n个自然数组成的多重集合S，设计算法求其众数和重数。例如：给出 S = [1,2,3,4,5,2,2] S其众数是2，重数是3

编程要求

本关的编程任务是用分治法编写求众数及其重数的函数
int GetMode(int a[],int p,int r,int &Count)
返回值为数组a[p]~a[r]之间的众数,参数Count存放众数对应的重数。

主函数如下：

#include<iostream>
using namespace std;
int main()
{
int n,Cnt,mode;
cin>>n;
int *a = new int[n];
for(int i = 0; i < n; i ++)
cin>>a[i];
mode = getMode(a,0,n-1,Cnt);
return 0;
}

测试说明

正确完成函数编写即可。

开始你的任务吧，祝你成功！

答案：

void Partition(int a[], int p, int r,int x,int jizhun[])

{

int left = p , right = r;

while (left < right)

{

//从右边遍历找到第一个<=基准值的元素

while (a[right] > a[x] && right != left)//要注意，左右指针前进的顺序，因为以第一个元素为基准值，故右指针先走

{

if (a[right] == a[x])//判断等于为基准值的

jizhun[1]++;//基准值的重数

right--;

}

//从左边遍历找到第一个>基准值的元素

while (a[left] <= a[x] && left != right)

{

if (a[left] == a[x])

jizhun[1]++;

left++;

}

//交换位置，使左边的元素<=基准值，右边的元素>基准值

if (left != right)

{

int temp = a[left];

a[left] = a[right];

a[right] = temp;

}

//基准值归位

int temp = a[right];

a[right] = a[x];

a[x] = temp;

jizhun[0] = right;//存基准值下标

}

//函数返回值：众数

int getMode(int a[], int p, int r, int& Cnt)

{

int Cnt_m=1,Cnt_l = 1, Cnt_r = 1;//存左右边、基准值元素的重数

int mod_m=0,mod_l = 0, mod_r = 0;//存左右、基准值众数

int* jizhun = new int[2];//数组0存基准值下标，1存基准值重数

jizhun[0] = 0; jizhun[1] = 1;//设置初始值

//设置基准值为数组第一个元素

Partition(a,p,r,p,jizhun);//数组第一个元素为基准值，对数组进行划分

mod_m = a[p]; Cnt_m = jizhun[1];//基准值的重数和众数

int leftsize = jizhun[0] - jizhun[1] + 1;//基准值左边元素个数

int rightsize = r - jizhun[0];//基准值右边的元素个数

if (leftsize > jizhun[1])//左边元素个数多，递归求左边元素

{

mod_l=getMode(a, p, (jizhun[0] - jizhun[1]), Cnt_l);

}

if (rightsize > jizhun[1])//右边元素个数多，递归求右边元素

{

mod_r=getMode(a, (jizhun[0] + 1), r, Cnt_r);

}

//比较三者重数--特殊情况没有考虑---》即重数均为1或者有两个数的重数相等，再加一部分比较重数相等情况下的众数即可，这里可以单独写一个比较函数.

if (Cnt_l > Cnt_r)

{

if (Cnt_l > Cnt_m)

{

Cnt = Cnt_l;

return mod_l;

}

else

{

Cnt = Cnt_m;

return mod_m;

}

else

{

if (Cnt_r > Cnt_m)

{

Cnt = Cnt_r;

return mod_r;

}

else

{

Cnt = Cnt_m;

return mod_m;

}

第8关：求逆序对数

任务描述

对于不同的排序可以用逆序来评价它们之间的差异。一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序,(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1),因此，该排列的逆序数就是8。显然，由1,2,...,n，n个数组成的n!个排列中，最小逆序数是0，对应排列1,2,...,n。最大逆序数是2n(n−1)，对应排列n,n−1,...,2,1。逆序数越大与原始排列差异越大。

编程要求

根据提示，在右侧编辑器补充代码。

输入格式

第一行是一个整数n，表示该排列有n个数（n<=100000)。

第二行是n个不同的正整数，之间以空格隔开，表示该排列。

输出格式

输出该排列的逆序数。

输入输出样例

测试输入：

6 2 6 3 4 5 1 预期输出： 8

提示

结合归并排序做

开始你的任务吧，祝你成功！

答案：

//归并排序及求逆序对
#include<iostream>
using namespace std;
#define N 1000005
int a[N], b[N];//b为辅助数组
long long cnt;
void merge_sort(int l, int r)
{
	// 如果整个区间中元素个数大于1，则继续分割
	if (r - l > 0)
	{
		// 1、尽量划分为数量相等的2个子序列，并排序
		int mid = (l + r) / 2;
		merge_sort(l, mid);
		merge_sort(mid + 1, r);

		// 2、将2个有序的序列合并成一个有序序列，在左右有序的子数组合并的同时，统计逆序对数
		/*********Begin***********/
          int i = l, j = mid + 1, k = l;  
        while (i <= mid && j <= r)  
        {  
            if (a[i] <= a[j])  
                b[k++] = a[i++];  
            else  
            {  
                b[k++] = a[j++];  
                // 计算逆序对数量，即左半部分中剩余的元素数量  
                cnt += mid - i + 1;  
            }  
        }  
        // 复制剩余的元素  
        while (i <= mid)  
            b[k++] = a[i++];  
        while (j <= r)  
            b[k++] = a[j++]; 

  
       /*********End***********/
		// 3、将辅助数组b中排好序的元素复制到a中
		for (i = l; i <= r; i++)
			a[i] = b[i];
	}
}
int main()
{
	int n;
	while (cin >> n)
	{
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		cnt = 0;
		merge_sort(1, n);

		cout << cnt << endl;
	}
	return 0;
}

分治法-二分查找

第1关：排序矩阵查找

题目描述

《程序员面试金典（第 6 版）》

任务描述

本关任务：给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。

示例:

现有矩阵 matrix 如下：

[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]

给定 target = 5，返回 true。

给定 target = 20，返回 false。。

提示

可以按每行二分查找，复杂度是O(mlgn) 也可以按每列二分查找,复杂度是O(nlogm)

编程要求

根据提示，在右侧编辑器补充代码。

测试说明

输入格式：第一行是三个正整数m,n，x.随后m行，每行n列输出格式：true 或者 false

测试输入： 5 5 5 1 4 7 11 15 2 5 8 12 19 3 6 9 16 22 10 13 14 17 24 18 21 23 26 30 预期输出： Yes

开始你的任务吧，祝你成功！

答案：

#include<iostream> 
using namespace std;
const int N = 100;
int m,n;

bool binarySearch(int arr[], int target, int left, int right) {  
    while (left <= right) {  
        int mid = left + (right - left) / 2;  
        if (arr[mid] == target) return true;  
        else if (arr[mid] < target) left = mid + 1;  
        else right = mid - 1;  
    }  
    return false;  
}  
  
bool searchMatrix(int matrix[][N], int target) {  
    for (int i = 0; i < m; i++) {  
        // 每一行的最后一个元素如果小于目标值，那么目标值肯定不在这一行  
        if (matrix[i][n - 1] < target) continue;  
        // 每一行的第一个元素如果大于目标值，那么目标值肯定不在这一行  
        if (matrix[i][0] > target) break;  
        // 在当前行执行二分查找  
        if (binarySearch(matrix[i], target, 0, n - 1)) {  
            return true;  
        }  
    }  
    return false;  
}  
int main()
{
    int x;
    int matrix[N][N];
    cin>>m>>n>>x;
    for(int i = 0; i < m; i ++)
      for(int j = 0; j < n; j ++)
         cin>>matrix[i][j];

    if(searchMatrix(matrix,x))cout<<"true"<<endl;
    else cout<<"false"<<endl;
    return 0;

}

第2关：魔术索引

题目来源

《程序员面试金典（第 6 版）》魔术索引

任务描述

本关任务：在数组A[0...n−1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。(数据没有重复) 例如：输入：nums = [0, 1, 3, 4, 5] 输出：0 说明: 0下标的元素为0,1的下标为1,0是满足条件索引值最小的一个。输入：nums = [-1, 1, 3] 输出：1

编程要求

根据提示，在右侧编辑器补充代码。

测试说明

输入格式：输入两行，第一行一个正整数n,第二行n个有序正整数输出格式：输出一个整数，魔术索引的下标或者-1.

测试输入： 4 -5 -2 0 3 预期输出： 3

提示：

遍历一遍时间复杂度最高O(n)
可以利用二分查找思想设计O(lgn)算法

开始你的任务吧，祝你成功！

答案：

#include<iostream>
using namespace std;
const int N = 100000;

int MagicIndex(int a[],int n)
{
/***********Begin*********/
for(int i=0;i<n;i++)
{
  if(i==a[i])
  return i;
}
return -1;

/***********End*********/
}
int main()
{
    int n,a[N],mi;
    cin>>n;
    for(int i = 0; i < n; i ++)
      cin>>a[i];
   mi = MagicIndex(a,n);
    cout<<mi<<endl;
    return 0;

}

第3关：搜索旋转数组

题目来源

任务描述

本关任务：搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。示例：输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5 输出: 8（元素5在该数组中的索引）

第4关：寻找两个正序数组的中位数

题目来源

力扣题库 4.寻找两个正序数组的中位数困难

任务描述

本关任务：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为 O(log (m+n)) 。示例 1：输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2

数据范围

0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -1e6 <= nums1[i], nums2[i] <= 1e6

动态规划课堂案例

第1关：01背包问题

任务描述

本关任务：给定n种物品和一背包。物品i占的容量是vi，其价值为wi，背包的总容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大

输入输出

输入格式：第一行两个整数n和c,物品个数和背包容量；随后n行表示每个物品的价值vi，重量wi 输出格式：能达到的最大价值

输入样例 5 10 6 2 3 2 5 6 4 5 6 4

输出样例： 15

开始你的任务吧，祝你成功！

答案：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
 int v[N],w[N];
int solve(int n,int c)
{
/**********Begin***********/
int k[N][N];
for(int i=1;i<=n;i++)
{
    for(int j=0;j<=c;j++)
    {
      if(w[i]>j)
      {
      k[i][j]=k[i-1][j];
      }
      else
      {
          if(k[i-1][j]>k[i-1][j-w[i]]+v[i])
          k[i][j]=k[i-1][j];
          else
          k[i][j]=k[i-1][j-w[i]]+v[i];
      }
    }
   
}

 return k[n][c];

/**********End***********/
}

int main()
{
    int n,c;
	cin>>n>>c;
	for(int i = 1; i <= n; i ++)
	  cin>>v[i]>>w[i]; 
	cout<<solve(n,c)<<endl;
	return 0;
}

第2关：最长公共子序列

任务描述

本关任务：一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。给出两个序列X和Y，求其最长公共子序列长度。

输入输出

输入格式：两行，每行一个字符串 输出格式：一个整数m,代表两个字符串的最长公共子序列长度

输入样例： BDCABA ACBDAB

预期输出： 4

开始你的任务吧，祝你成功！

第3关：矩阵连乘问题

任务描述

本关任务：给定n个矩阵

解释

A1,A2,…,An，其中Ai与Ai+1是可乘的，i=1,2…,n−1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

测试说明

输入格式 第1行一个正整数n，是矩阵个数；第2行是n+1个正整数，表示他们的维数 输出格式 最少乘法次数

测试输入： 6 35 10 25 5 45 10 15 预期输出： 8625

开始你的任务吧，祝你成功！

答案：

#include <iostream>
using namespace std; 
const int N = 110;
int n;
int p[N],m[N][N];

int MatrixChain(int n)
{
/*******Begin********/

for(int i=1;i<=n;i++)
m[i][i]=0;
for(int len=2;len<=n;len++)
{
  for(int i=1;i<=n-len+1;i++)
  {
    int j=i+len-1;
    int cost;
    m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
    for(int k=i+1;k<j;k++)
    {
      cost=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
      if(m[i][j]>cost)
      m[i][j]=cost;
    }
  }
}
return m[1][n];



/*******End********/
}

int main()
{
   int min;
    cin >> n;  
    for(int i = 0; i <= n; i++)
      cin>>p[i];
	
	min = MatrixChain(n);
    printf("%d",min);
	

	return 0;
}

第4关：凸多边形最优三角剖分

任务描述

本关任务：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w，设为

解释

w(vivjvk)=∣vivj∣+∣vjvk∣+∣vivk∣，要求确定该凸多边形的三角剖分，使得该三角剖分有最小的权之和。

编程要求

根据提示，在右侧编辑器补充代码。

测试说明

输入格式 第一行一个正整数，表示多边形顶点数； 输出格式 三角剖分的最小权值和 测试输入： 6 0 2 2 3 1 4 2 0 1 5 2 3 2 1 0 2 1 4 3 5 2 0 6 2 1 2 1 6 0 1 4 3 4 2 1 0 预期输出： 24

开始你的任务吧，祝你成功！

答案：

#include<iostream> 
using namespace std; 
const int N = 110;
int weight[N][N];//权值的邻接矩阵
int t[N][N];
int n;          //顶点个数


int w(const int a, const int b, const int c)
{//三角形权值函数
    return weight[a][b] + weight[b][c] + weight[c][a];
}

int minest_weight_val()
{
 /**********Begin**********/
 int mi=0;
 for(int i=1;i<=n;i++)
 t[i][i]=0;
 for(int r=2;r<=n;r++)
 {
   for(int i=1;i<=n-r+1;i++)
   {
     int j=i+r-1;
     t[i][j]=t[i+1][j]+w(i-1,i,j);
     for(int k=i+1;k<=i+r-1;k++)
     {
       int u=t[i][k]+t[k+1][j]+w(i-1,k,j);
       if(u<t[i][j])
       t[i][j]=u;
     }
     if(t[i][j]>mi)
     mi=t[i][j];
   }
 }
return mi;



  /**********End**********/
}
int main()
{
    int min;
    cin>>n;  
   for(int i = 0; i < n; i ++)
    for(int j = 0; j < n; j ++)
       cin >> weight[i][j];  
  min = minest_weight_val();
  cout<<min;
  return 0;

}

第5关：最优二叉搜索树

任务描述

本关任务：有序集

解释

S={x1,..,xn}的二叉搜索树利用二叉树的节点来存储有序集中的元素。 二叉搜索树的性质：

若它的左子树不空，则左子树上所有内节点的值均小于它的根节点的值；
若它的右子树不空，则右子树上所有内节点的值均大于它的根节点的值；
它的左、右子树也分别为二叉搜索树
二叉树的叶节点是形如
解释
xi,xi+1的开区间。

假设有序集

解释

S={x1,..,xn}用二叉搜索树存储，每个内节点存储元素xi，叶节点存储形如

解释

xi,xi+1的开区间。

内节点xi的存取概率bi
叶节点
解释
xi,xi+1的存取概率ai
解释
(a0,b1,a1,…,bn,an)称为集合S的存取概率分布。

在所有表示S的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树

第6关：最大子段和

任务描述

本关任务：给定由n个整数（可能为负数）组成的序列

解释

a1,a2 ,..,an，求该序列形如

解释

∑k=1jak的子段和的最大值。当所有整数均为负整数时，定义其最大字段和为0。例如：

编程要求

根据提示，在右侧编辑器补充代码。

输入输出

输入格式：第一行为正整数N,随后一个长度为n的整数序列 输出格式：最大子段和sum

测试输入： 6 -2 11 -4 13 -5 -23 预期输出： 20

开始你的任务吧，祝你成功！

答案：

#include<iostream> 
using namespace std; 
const int N = 1000010;
int a[N];
int n;

int MaxDPSum(){
	/******Begin********/
int sum=0,b=0;
for(int i=0;i<n;i++)
{
    if(b>0)
    b=b+a[i];
    else
    b=a[i];
    if(b>sum)

    sum=b;
}
return sum;



    /*******End********/
}


int main()
{
    int maxsum;
    cin>>n; 
    for(int i = 0; i < n; i ++)
        cin>>a[i];
    maxsum = MaxDPSum();
    cout<<maxsum<<endl;
    return 0;
}

动态规划进阶练习

第1关：石子合并

任务描述

沿着河岸摆放 N 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。例如:4堆石子4,5,9,4，可以按(((4,5),9),4)合并。

第一次合并得分是9分，合并之后石子堆是9,9,4
第二次合并得分是18分，合并之后石子堆是18,4
第三次合并得分是22分，合并之后石子堆是22
三次合并总得分49

试设计出一个算法,计算出将 N 堆石子合并成 1堆的最小得分和最大得分。

测试说明

输入格式

数据的第 1行是正整数 N，表示有N 堆石子。

第 2行有 N 个整数，第i 个整数 ai 表示第i 堆石子的个数。

输入格式

输出共 2 行，第 1 行为最小得分，第 2行为最大得分。

样例输入

4 4 5 9 4

样例输出

44 54

提示

1≤N≤100，

解释

0≤ai≤20。

第2关：基因检测

任务描述

本关任务：找出两个串的最长公共子串的长度。

用一个字符串表示一段基因，例如：CTATGGGTTT。两段基因的相似度定义为它们所包含的最大公共子串的长度。

例如：CCTTGG和TGGGC的最大公共子串为TGG，它的长度为3，则我们称CCTTGG和TGGGC的相似度为3。现给定两段基因，要求计算它们的相似度。

编程要求

在右侧编辑器中有一个函数Similar，它有两个参数str1，str2，是两个字符串，长度不超过50。

请你在这个函数中，计算并输出这两个字符串的相似度。

输入数据由评测系统读取，并传递给Similar函数。具体见测试说明。

测试说明

平台会对你编写的代码进行测试：

测试输入： CCCCC TTTTTGGGGGCC 预期输出： 2

测试输入： ACTGGG DDD 预期输出： 0

每组输入有两个，是两个字符串，分别对应str1和str2。

开始你的任务吧，祝你成功！

答案：

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
void Similar(char *str1,char *str2)
{
	/**********   Begin   **********/
    int len1=strlen(str1),len2=strlen(str2);
    int a[len1][len2];
    for(int i=0;i<len1;i++){
        for(int j=0;j<len2;j++){
            if(str1[i]==str2[j]){
                a[i][j]=1;
            }
            else{
                a[i][j]=0;
            }
        }
    }
    int max=0;
    for(int i=0;i<len1;i++){
        for(int j=0;j<len2;j++){
            if(a[i][j]==1){
                int f=1,m=i+1,n=j+1;
                while(m<len1 && n<len2 && a[m][n]==1){
                    m++;
                    n++;
                    f++;
                }
                max=max>f?max:f;
            }
        }
    }
	printf("%d",max);
	
	
	/**********   End   **********/
}

第3关：药剂稀释

任务描述

本关任务：找出一个序列中的最长下降子序列其中的元素个数。

医院里有一种药剂，其可以稀释成不同的浓度供病人使用，并且对于已知浓度的该药剂，使用时只能稀释不能增加浓度。

由于这种药需求量较大，同一瓶药剂只能给某个病人以及排在他后面的若干人使用。不同的病人对药物的浓度要求可能不同。

现在为了最大限度的利用每一瓶药剂（不考虑容量），已知n个病人所需药物浓度的序列，请计算出一瓶药剂能最多使用的人数。

编程要求

在右侧编辑器中有一个函数Cal，它有两个参数arr和n。

arr中包含n个病人对药物浓度的要求。

请你在这个函数中补充代码，计算并输出一瓶药剂能最多使用的人数。

输入数据由评测系统读取，并传递给Cal函数。具体见测试说明。

测试说明

平台会对你编写的代码进行测试：

测试输入： 6 0.7 0.9 0.6 0.8 0.8 0.4

预期输出： 4

每组输入有两行，第一行有一个数n，第二行的n个数为数组的内容。

开始你的任务吧，祝你成功！

答案：

#include <iostream>
#include <algorithm>
using namespace std;
 
void Cal(double arr[],int n)
{
    /**********   Begin   **********/
	

      int a[n];
    int t=0;
    int max=0;
    for(int i=n-1;i>=0;i--)
    {
        a[i]=1;
        for(int j=i+1;j<n;j++)
        {
            if(arr[j]<=arr[i])
            {
            t=a[j]+1;
            if(a[i]<=t)
            a[i]=t;
            }
        }
        if(max<=a[i])
        max=a[i];
    }
	//补充代码完成任务
printf("%d",max);
	/**********   End   **********/
}

第4关：找相似串

任务描述

本关任务：找出最接近的相似串。

一般情况下，度量两个串S1和S2的相似性，可以通过从一个串变换成另一个串所需要的最少操作次数来衡量，需要的操作次数越少，则越相似。

假设从一个串变化成另一个串所允许的操作只有两种：插入一个字符或者删除一个字符。无论是插入还是删除一个符号，均算作一次操作。

现给你一个串S，和一个串的集合T，让你找出集合T中与S最相似的串。

编程要求

右侧编辑器中有一个函数Similar，请在这个函数中读取数据完成任务。

输入数据由学员处理。输入的第一行为一个串S，第二行是一个整数n，范围0 < n < 20，表示接下来集合T中的串的个数。接下来n行，每行为一个串。

注：所有字符串的长度不超过50。

请输出T中与S最相似的串，如果有多个就输出多个串（按照输入时的顺序），每个串占一行。具体见测试说明。

测试说明

平台会对你编写的代码进行测试：

测试输入： abcd 4 abd abdc abed aebcd

预期输出： abd aebcd

提示：对于第一个串abd，在b后插入一个c就可以变成abcd，操作次数为1次。第二个串abdc，删除d后面的c，在d前面增加一个c，即可变成abcd，操作次数为2次。第三个串abed，删除d前面的e，在d前面增加一个c，即可变成abcd，操作次数为2次。第四个串aebcd，删除a后面的e即可变成abcd，操作次数为1次。

开始你的任务吧，祝你成功！

答案：

#include <iostream>
#include <cstring>
using namespace std;
const int MAX=60;
void Similar()
{
	/**********   Begin   **********/
	char s[MAX];
	int n,end;
	cin >> s>>n;//读取主串和子串个数
	int len_s = strlen(s);
	char arr[20][MAX];
	int caozuo[20];//存操作次数
	int dp[MAX][MAX];//用数组dp[i][j]表示，子串从1-i转换到主串的操作数。
	for (int i = 0; i < n; i++)//读取子串
	{
		cin>>arr[i];
	}	
	for (int i = 0; i < len_s; i++)
	{
		dp[0][i] = i;  //处理边界
	}
 
	for (int k = 0; k < n; k++)//第k个子串
	{
		int len = strlen(arr[k]);//子串长度
		//初始化
		for (int j = 0; j < len; j++)
			dp[j][0] = j;
 
		for (int i = 1; i < len_s; i++)//i为主串下标
		{
			for (int j = 1; j < len; j++)//j为子串下标
			{
				if (s[i] == arr[k][j])
					dp[i][j] = dp[i - 1][j - 1];
				else
					dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
			}
		}
		caozuo[k] = dp[len_s-1][len-1];//存每个子串的最小操作数
	}
	end = caozuo[0];
	for (int i = 1; i < n; i++)
		end = min(end, caozuo[i]);  //找到最小操作数
	for (int i = 0; i < n; i++)
	{
		if (caozuo[i] == end)
			cout << arr[i] << endl;  //输出对应串
	}
 
	/**********   End   **********/
}

第5关：聪明的寻宝人

任务描述

本关任务：计算寻宝人所能带走的宝物的最大价值。

一个寻宝人在沙漠中发现一处神秘的宝藏，宝藏中共有n个宝物（n不超过20），每个宝物的重量不同，价值也不同，宝物i的重量是wi，其价值为vi。

寻宝人所能拿走的宝物的总重量为m（m不超过50）。请帮助寻宝人写一个程序，计算寻宝人能够获得的最大总价值。

编程要求

在右侧编辑器中有一个函数MaxValue，它有四个参数values，weights，n，m。

values和weights分别存放了n件宝物的价值和重量，m为寻宝人所能携带的最大重量。

请在这个函数中补充代码，计算并输出寻宝人所能获得的最大总价值。

输入数据由评测系统读取，并传递给MaxValue函数。具体见测试说明。

测试说明

平台会对你编写的代码进行测试：

测试输入： 3 10 3 4 4 5 5 6

预期输出： 11

每组输入有多行，第一行有两个数n和m，分别为宝石数量和寻宝人载重。下面有n行数据，每一行有两个数，分别是宝石重量和宝石价值。

开始你的任务吧，祝你成功！

答案：

#include <iostream>

using namespace std;

int num[20][20];

void MaxValue(int values[], int weights[], int m, int n)

{
    /**********   Begin   **********/

    int jmax = min(weights[m] - 1, n);

    for (int j = 0; j <= jmax; j++) {
        num[m][j] = 0;

    }

    for (int j = weights[m]; j <= n; j++)

        num[m][j] = values[m];

    for (int i = m - 1; i > 1; i--) {
        jmax = min(weights[i] - 1, n);

        for (int j = 0; j <= jmax; j++)

            num[i][j] = num[i + 1][j];

        for (int j = weights[i]; j <= n; j++)

            num[i][j] = max(num[i + 1][j], num[i + 1][j - weights[i]] + values[i]);

    }

    num[1][n] = num[2][n];

    if (n >= weights[1]) {
        num[1][n] = max(num[1][n], num[2][n - weights[1]] + values[1]);

    }

    cout << num[1][n];
}