本文主要是介绍【强训笔记】day22，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
NO.1
思路：将情况全部枚举出来。
代码实现：
#include <iostream>
#include<string>
using namespace std;string a,b;
int main()
{cin>>a>>b;int m=a.size(),n=b.size();int ret=m;for(int i=0;i<=n-m;i++){int tmp=0;for(int j=0;j<m;j++){if(a[j]!=b[i+j]){tmp++;}}ret=min(ret,tmp);}cout<<ret<<endl;return 0;
}
NO.2
思路：先找出数组中的最大值，如果可以被最大值整除说明较小值可以变为最大值，但是它们的商必须的是2的n次方，数组中的数都满足就输出YES，否则输出NO。
代码实现：
#include <iostream>
using namespace std;int arr[51];
int n;
int b;
bool fun()
{for(int i=0;i<n;i++){if(b%arr[i]) return false;int x=b/arr[i];if(x&(x-1)) return false;}return true;
}int main() {cin>>n;for(int i=0;i<n;i++){cin>>arr[i];b=max(b,arr[i]);}if(fun()) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
NO.3
思路：动态规划背包问题。dp[i][j]表示容量不超过j的所装的总容量，推导dp状态转移方程就可以了。
代码实现：
#include <iostream>
using namespace std;
const int N = 35, M = 2e4 + 10;
int n, v;
int arr[N];
int dp[N][M];
int main()
{cin >> v >> n;for (int i = 1; i <= n; i++){cin >> arr[i];}for (int i = 1; i <= n; i++){for (int j = 0; j <= v; j++){dp[i][j] = dp[i - 1][j];if (j >= arr[i]){dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i]] + arr[i]);}}}cout << (v - dp[n][v]) << endl;return 0;
}
这篇关于【强训笔记】day22的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
