http://codeforces.com/contest/761/problem/C

对于每一个字符串，可以预处理出其到达数字，字母，和特殊符号所需的最小步数。

然后就是在n个东西中，选出数字、字母和特殊符号，至少一个，所需的最少步数。

因为第一个选了数字的话，它就不能选字母的了，然后比赛的时候发现这就是二分图，然后就上了km的模板。（太笨了我）

虽然过了，但是明显正解不是这个。

#include
#include
#include
#include
#include
#include
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include
#include
#include
#include
#include

int match[maxn];//match[col] = row
int vx[maxn], vy[maxn];
int fx[maxn], fy[maxn];
int dfs (int u, int m) {
vx[u] = ;
int i;
for (i = ; i <= m; i++) { //筛选n个 导航员 col的值 if (vy[i] == && fx[u] + fy[i] == e[u][i]) { vy[i] = ; if (match[i] == || dfs(match[i], m)) { match[i] = u; // match[col]=row; return ;//搭配成功 } } } return ;//我找不到啊，后面，就会执行km } void do_km(int n, int m) { // int i, j; int d = -inf; for (i = ; i <= n; i++) { //遍历每一个驾驶员 row的值 if (vx[i] == ) { for (j = ; j <= m; j++) { //对他进行遍历导航员 col的值 if (!vy[j]) { if (d < (fx[i] + fy[j] - e[i][j])) { d = fx[i] + fy[j] - e[i][j]; } } } } } for (i = ; i <= n; i++) { if (vx[i] == ) { fx[i] -= d; vx[i] = ; //请0 } if (vy[i] == ) { // fy[i] += d; vy[i] = ; //情0 } } return ; } int anskm(int n, int m) { memset(vx, , sizeof(vx)); memset(vy, , sizeof(vy)); memset(fx, , sizeof(fx)); memset(fy, , sizeof(fy)); memset(match, , sizeof(match)); //km算法的一部分，先初始化fx，fy for (int i = ; i <= n; i++) { //遍历每一个驾驶员 row的值 fy[i] = ; fx[i] = inf; //无穷小 for (int j = ; j <= m; j++) { //遍历每一个导航员 col的值 if (fx[i] > e[i][j]) { //默契值
fx[i] = e[i][j];
}
}
}
for (int i = ; i <= n; i++) { //遍历每一个驾驶员 row的值
memset(vx, , sizeof(vx));
memset(vy, , sizeof(vy));
while (!dfs(i, m)) {//如果他找不到搭配，就实现km算法
do_km(n, m);//km完后，还是会对这个想插入的节点进行dfs的,因为他还没搭配嘛
}
}
int ans = ;
for (int i = ; i <= m; i++) //遍历导航员，col的值
ans += e[match[i]][i];//输入的row是驾驶员，col是导航员
//match[i]:导航员i和驾驶员match[i]搭配了 match[col]=row;
return ans;
}

void work() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= ; ++i) { for (int j = ; j <= ; ++j) { e[i][j] = ; } } for (int i = ; i <= n; ++i) { scanf("%s", str[i] + ); int a = , b = , c = ; int len = m; for (int j = ; str[i][j]; ++j) { if (str[i][j] >= '' && str[i][j] <= '') { a = min(a, j - ); } else if (str[i][j] == '#' || str[i][j] == '*' || str[i][j] == '&') { b = min(b, j - ); } else { c = min(c, j - ); } } for (int j = len; j >= ; j--) {
if (str[i][j] >= '' && str[i][j] <= '') {
a = min(a, len - j + );
} else if (str[i][j] == '#' || str[i][j] == '*' || str[i][j] == '&') {
b = min(b, len - j + );
} else {
c = min(c, len - j + );
}
}
e[i][] = a;
e[i][] = b;
e[i][] = c;
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 1; j <= n; ++j) {
// cout << e[i][j] << " ";
// }
// cout << endl;
// }
cout << anskm(n, n) - (n - ) * << endl;
}

int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}

km

正解因该是一个dp

dp[i][2][2]][2]表示在前i个字符串中，选出了数字（0 or 1）、字母、特殊符号所需的最小步数。

转移

dp[now][a][b][c] = min(dp[now][a][b][c], dp[!now][a][b][c]); //保留上次的最小值。

然后对于每一个a、b、c

dp[now][a][b][c] = min(dp[now][a][b][c], dp[!now][a - 1][b][c] + e[i][1]);之类的。

一开始还担心会不会使得同一个字符串，既选了数字，也选了字母。

然后是不会的，因为需要选数字的时候，是从dp[!now][a - 1][b][c]转移过来的，也就是从上一唯的b、c转过来。所以不会有重复。

#include
#include
#include
#include
#include
#include
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include
#include
#include
#include
#include

int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
work();
return ;
}