动态规划（2）

动态规划（2）

1、聪明的寻宝人

#include 
using namespace std;
void MaxValue(int values[], int weights[], int n, int m) {
    int dp[21][51] = {0};
    for (int i = 1; i  n; ++i) {
        for (int j = 1; j  m; ++j) {
            if (weights[i - 1]  j) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i -服务器托管 1]] + values[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout  dp[n][m]  endl;
 }

2、基因检测

#include 
#include 
#include 
#include 
using namespace std;

void Similar(char *str1, char *str2) {
    int m = strlen(str1);
    int n = strlen(str2);
    int dp[51][51] = {0};
    int maxLen = 0;
    for (int i = 1; i  m; ++i) {
        for (int j = 1; j  n; ++j) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1]服务器托管[j - 1] + 1;
                maxLen = max(maxLen, dp[i][j]);
            } else {
                dp[i][j] = 0; 
            }
        }
    }
    cout  maxLen ;
}

3、药剂稀释

#include 
using namespace std;

void Cal(double arr[],int n)
{
    /**********   Begin   **********/
	
	//补充代码完成任务
    int dp[n];
    for(int i=0;in;i++) dp[i]=1;
    for(int i=n-2;i>=0;i--){
        for(int j=i+1;jn;j++){
            if(arr[i]>=arr[j]) dp[i]=dp[i](dp[j]+1)?(dp[j]+1):dp[i];
        }
    }
    int max=1;
    for(int i=0;in;i++){
      
        if(maxdp[i]) max=dp[i];
    }
    printf("%d",max);
	/**********   End   **********/
}

4、找相似串

#include 
#include 
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   **********/
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: OD_2024_C卷_100分_65、整型数组按个位值排序【JAVA】【逻辑分析】

题目描述 小明今年升学到了小服务器托管网学1年级来到新班级后，发现其他小朋友身高参差不齐，然后就想基于各小朋友和自己的身高差，对他们进行排序，请帮他实现排序。 输入描述 第一行为正整数 h和n，0 输出描述 输出排序结果，各正整数以空格分割， 和小明身高差绝对…