• 欢迎光临~

# 洛谷P2758 编辑距离

## 题目描述

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

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

(A, B) 均只包含小写字母。

## 样例 #1

### 样例输入 #1

``````sfdqxbw
gfdgw
``````

### 样例输出 #1

``````4
``````

## 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 普及组] 摆花

## 样例 #1

### 样例输入 #1

``````2 4
3 2
``````

### 样例输出 #1

``````2
``````

## 提示

【数据范围】

NOIP 2012 普及组 第三题

## 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;
}
``````