目录
064:添加字符
065:数组变换
066:装箱问题
064:添加字符
添加字符_牛客笔试题_牛客网 (nowcoder.com)
题目：
题解：
枚举所有A，B字符串可能的对应位置，得出对应位置不同字符数量的最小情况
两字符串的字符数量差n-m，长字符串可从 [0,n-m] 位置作为起始下标。
#include <iostream>
#include<algorithm>
#include<string>
using namespace std;
string A,B;
int main()
{cin>>A>>B;int m=A.size(), n=B.size();int ret=50;for(int i=0;i<=n-m;i++){int tmp=0;for(int j=0;j<m;j++){if(B[i+j]!=A[j]) //不改变i的情况，A，B一起向后遍历{tmp++;}}ret=min(tmp,ret);}cout<<ret<<endl;return 0;
}
065:数组变换
数组变换__牛客网 (nowcoder.com)
题目：
题解：
将数组排序后由大到小遍历，取相邻两个。将较小的值不断乘以2，如果某次结果等于较大的值，则符合条件继续向后取相邻两个数，如果不断乘以2最后只会大于较大的值时，则整个数组不符合条件。
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL arr[51];
int n;
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>arr[i];}sort(arr,arr+n);int i=n-1;for(;i>0;i--){while(arr[i-1]<arr[i]){arr[i-1]*=2;}if(arr[i-1]==arr[i]){continue;}else{break;}}if(i==0) cout<<"YES"<<endl;else cout<<"NO"<<endl;return 0;
}
066:装箱问题
[NOIP2001]装箱问题 (nowcoder.com)
题目：
题解：
01背包简单应用：
#include<iostream>using namespace std;
int V,n;
int arr[31],dp[31][20010]={0};int main()
{cin>>V>>n;for(int i=1;i<=n;i++)//从下标1开始，方便dp边界填表{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;
}//优化空间版
#include<iostream>using namespace std;
int V,n;
int arr[31],dp[20010]={0};int main()
{cin>>V>>n;for(int i=1;i<=n;i++)//从下标1开始，方便dp边界填表{cin>>arr[i];}for(int i=1;i<=n;i++){for(int j=V;j>=arr[i];j--){dp[j]=max(dp[j],dp[j-arr[i]]+arr[i]);}}cout<<(V-dp[V])<<endl;return 0;
}
