1.添加字符
求最少不相等的位数，可以先求最多相等的位数。
在添加字符之前，A和B最多相等的位数是多少？由于A后面可以添加字符，也就使得A字符可以在B的任意一个位置开始比较。遍历一遍这个比较的起点，从这个起点开始跟A比较，看有多少相等的。用一个变量维护这个添加字符前最多相等的数量。
添加字符后呢？由于是可以添加任何字符，我们默认添加多少，就有多少个相等，即两个字符的长度差。
代码：
#include <iostream> #include<vector> #include<string> using namespace std; int main(){ string a; string b; cin>>a>>b; int n1=a.size(); int n2=b.size(); int ans=0; for(int i=1;i+n1-1<=n2;i++){ int pos=i; int cnt=0; for(int j=1;j<=n1;j++,pos++){ if(a[j-1]==b[pos-1]){ cnt++; } } ans=max(ans,cnt); } cout<<n2-(n2-n1+ans)<<endl; return 0; }
2.数组变换
排个序，遍历一遍数组，看当前元素的前一个元素是否能通过不断乘2来等于它。如果不能就直接NO
代码：
#include <iostream> #include<vector> #include<algorithm> using namespace std; typedef long long LL; bool isfun(LL x,LL y){ if(x==y)return true; int p=2; while(x<y){ x=x*p; } if(x==y)return true; return false; } int main() { int n; cin>>n; vector<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; } sort(a.begin(),a.end()); int f=0; for(int i=1;i<n;i++){ if(!isfun(a[i-1],a[i])){ f=1; break; } } if(f)cout<<"NO"<<endl; else cout<<"YES"<<endl; return 0; }
3.装箱问题
最小剩余空间，即v-最大利用空间。
01背包，只不过最大价值变成了最大利用空间。换一下值而已。
代码：
#include <iostream> #include<vector> using namespace std; int main() { int v; int n; cin>>v>>n; vector<int> a(n+1); vector<vector<int>> f(n+1,vector<int>(v+1)); for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ for(int j=0;j<=v;j++){ if(j>=a[i])f[i][j]=max(f[i-1][j-a[i]]+a[i],f[i-1][j]); else f[i][j]=f[i-1][j]; } } cout<<v-f[n][v]; return 0; }
