day 2

写了一道简单的dp，题目：https://codeforces.com/problemset/problem/2050/E
题目大意：给你三个字符串a，b，c。每一次可以选a或b的开头一个字母加到答案字符串后面，选择的字母从原来的字符串删除，求答案字符串和c最少有几个不同。
很明显dp，在看数据量，a和b小于等于1000，可以想到n方的dp，dp数组为dp[i][j]，表示已经用了前i个，b已经用了前j个所得到的最小不同数量。
那么状态转移方程就很简单了
代码：

include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e3 + 10;

int dp[N][N];

void solve()
{
string a,b,c;
cin >> a >> b >> c;
int la = a.size(),lb = b.size();
memset(dp,114514,sizeof dp);
dp[0][0] = 0;
for(int i = 1;i<=la;i++)
{
dp[i][0] = dp[i-1][0] + (a[i-1] != c[i-1]);
}
for(int i = 1;i<=lb;i++)
{
dp[0][i] = dp[0][i-1] + (b[i-1] != c[i-1]);
}

for(int i = 1;i<=la;i++)
{for(int j = 1;j<=lb;j++){dp[i][j] = min(dp[i-1][j] + (a[i-1] != c[i+j-1]),dp[i][j-1] + (b[j-1] != c[i+j-1]));}
}
cout << dp[la][lb] << endl;

}

signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

int t;
cin >> t;
while (t--)solve();
return 0;

}