今天沉迷游戏，做两道简单一点的题。
洛谷P2758 编辑距离
题目描述
设 \(A\) 和 \(B\) 是两个字符串。我们要用最少的字符操作次数，将字符串 \(A\) 转换为字符串 \(B\)。这里所说的字符操作共有三种：
- 删除一个字符；
- 插入一个字符；
- 将一个字符改为另一个字符。
\(A, B\) 均只包含小写字母。
输入格式
第一行为字符串 \(A\)；第二行为字符串 \(B\)；字符串 \(A, B\) 的长度均小于 \(2000\)。
输出格式
只有一个正整数，为最少字符操作次数。
样例 #1
样例输入 #1
sfdqxbw
gfdgw
样例输出 #1
4
提示
对于 \(100 \%\) 的数据，\(1 \le |A|, |B| \le 2000\)。
思路
状态表示：\(f[i][j]\) 将 \(A[1-i]\) 和 \(B[1-j]\) 变为相同的操作数集合，求其中的最小值。
状态计算：如果实施的是删除操作，那么就是删除 \(A[i]\)，也就是 \(A[1-(i-1)]\) 和 \(B[1-j]\) 已经相同了，则操作数为 \(f[i-1][j]+1\)；如果实施的是增加操作，那么就是增加 \(B[i]\)，也就是 \(A[i]\) 后添加 \(B[i]\) 才和 \(B[1-j]\) 相同，则操作数为 \(f[i][j-1]+1\)；而如果是修改操作，也就是说 \(A[i-(i-1)]\) 和 \(B[1-(j-1)]\) 相同了，是否修改取决于 \(A[i]\) 和 \(B[j]\) 是否相同。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 20010;
typedef pair<int, int> PII;
typedef long long LL;
string A, B;
int f[N][N]; // f[i][j]将A[1-i]转变为B[1-j]的操作数集合
int main ()
{
cin >> A >> B;
A = "#" + A;
B = "#" + B;
int n = A.size() - 1, m = B.size() - 1;
for (int i = 1; i <= n; i ++)
f[i][0] = i;
for (int i = 1; i <= m; i ++)
f[0][i] = i;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); // 删除、增加
if (A[i] == B[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m] << endl;
return 0;
}
洛谷P1077 [NOIP2012 普及组] 摆花
题目描述
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 \(m\) 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 \(n\) 种花，从 \(1\) 到 \(n\) 标号。为了在门口展出更多种花，规定第 \(i\) 种花不能超过 \(a_i\) 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
输入格式
第一行包含两个正整数 \(n\) 和 \(m\)，中间用一个空格隔开。
第二行有 \(n\) 个整数，每两个整数之间用一个空格隔开，依次表示 \(a_1,a_2, \cdots ,a_n\)。
输出格式
一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 \(10^6+7\) 取模的结果。
样例 #1
样例输入 #1
2 4
3 2
样例输出 #1
2
提示
【数据范围】
对于 \(20\%\) 数据，有 \(0<n \le 8,0<m \le 8,0 \le a_i \le 8\)。
对于 \(50\%\) 数据，有 \(0<n \le 20,0<m \le 20,0 \le a_i \le 20\)。
对于 \(100\%\) 数据，有 \(0<n \le 100,0<m \le 100,0 \le a_i \le 100\)。
NOIP 2012 普及组 第三题
思路
类似于背包问题。
状态表示：\(f[i][j]\) 表示从 \(1-i\) 中选出 \(j\) 盆的方案集合，求的是方案数。
状态计算：\(f[i][j]\)，我们考虑第 \(i\) 种选的盆数 \(k\)，那么就有 \(f[i][j]=\sum{f[i-1][j-k]},0≤k≤min(a[i],j)\)。
这是一种朴素解法。其实状态表示可以使用滚动数组优化空间，状态计算可以使用前缀和优化时间，这里就不展开了。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110, MOD = 1e6 + 7;
typedef pair<int, int> PII;
typedef long long LL;
int n, m;
int a[N];
int f[N][N]; // f[i][j]表示从1-i中选出j盆的方案集合
int main ()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
scanf("%d", &a[i]);
f[0][0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= m; j ++)
for (int k = 0; k <= min(a[i], j); k ++)
{
f[i][j] = (f[i][j] + f[i - 1][j - k]) % MOD;
}
cout << f[n][m] << endl;
return 0;
}