上午
编辑距离（AcWing.899）
思路：同最短编辑距离，只不过要做 \(m\) 次。
code：
#include <bits/stdc++.h>
#define ll long long
#define N 1005
using namespace std;
inline ll read()
{
ll x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
return (f==1)?x:-x;
}//卡长
ll k=read(),t=read(),l,ans,cnt,maxn,f[N][N];
char s[N][N];
void init(ll n,ll m)
{
for(ll i=0;i<=maxn;i++)
{
if(i<=n) f[i][0]=i;
if(i<=m) f[0][i]=i;
}
}
ll check(char a[],char b[])
{
ll n=strlen(a+1),m=strlen(b+1);
maxn=max(n,m);init(n,m);
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=m;j++)
{
f[i][j]=min(f[i][j-1],f[i-1][j])+1;
f[i][j]=min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));//这里改进了一下
}
}
return f[n][m];
}//最短编辑距离
int main()
{
ios::sync_with_stdio(0);cout.tie(0);//卡长
for(ll i=0;i<k;i++) scanf("%s",s[i]+1);
while(t--)
{
ans=0;char ask[N];
scanf("%s",ask+1);l=read();
for(ll i=0;i<k;i++)
if(check(s[i],ask)<=l)
ans++;//统计答案
cout << ans << endl;
}
return 0;
}
下午
整数划分（AcWing.900）
做法1：01背包
#include <bits/stdc++.h>
#define ll long long
#define N 1005
#define mod 1000000007
using namespace std;
inline ll read()
{
ll x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
return (f==1)?x:-x;
}
ll n=read(),f[N];
int main()
{
f[0]=1;
for(ll i=1;i<=n;i++)
for(ll j=i;j<=n;j++)
f[j]=(f[j]+f[j-i])%mod;
cout << f[n];
return 0;
}
做法2：计数DP
-
状态表示
设f[i][j]表示所有总和是 \(i\)，并且能拆分成 \(j\) 个数的方案总数。 -
循环范围
\(i\) 表示总和，总和最多是 \(n\),因此 \(i\) 的循环范围是 1~\(n\)。
\(j\) 表示拆成多少个数，拆分最多能拆成 \(i\) 个（每个数都是1）,因此 \(i\) 的循环范围是 1~\(i\)。 -
状态转移
首先考虑把f[i][j]分成两个完全不重复的集合。
可以分成最小值为1的集合、最小值大于1的集合。最小值为1的集合如果减去最小值1，那总和就是 \(i\)-1，拆分后数的数量为 \(j\)-1。
最小值大于1的集合如果每个数都减去1，那总和就是 \(i\)-\(j\)，拆分后数的数量不变。f[i][j]就是这两个方案总数的和。可得，转移方程为：
f[i][j]=f[i-1][j-1]+f[i-j][j];
有了这些，就可以打出code：
#include <bits/stdc++.h>
#define ll long long
#define N 1005
#define mod 1000000007
using namespace std;
inline ll read()
{
ll x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
while(isdigit(c)){x=x*10+c-48;c=getchar();}
return (f==1)?x:-x;
}//卡长
ll n=read(),ans,f[N][N];
int main()
{
f[0][0]=1;
for(ll i=1;i<=n;i++)
for(ll j=1;j<=i;j++)
f[i][j]=(f[i-1][j-1]+f[i-j][j])%mod;//要取模
for(ll i=1;i<=n;i++) ans=(ans+f[n][i])%mod;//最后的答案就是不同拆分后数的数量的每种方案的和
cout << ans;
return 0;
}