今天沉迷游戏，做两道简单一点的题。

洛谷P2758 编辑距离

题目描述

设 (A) 和 (B) 是两个字符串。我们要用最少的字符操作次数，将字符串 (A) 转换为字符串 (B)。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

(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;
}