题解 | 字母收集

#include <iostream>
#include <vector>
using namespace std;

int GetScore(char c)
{
    if(c == 'l') return 4;
    else if(c == 'o') return 3;
    else if(c == 'v') return 2;
    else if(c == 'e') return 1;
    else return 0;
}

int main() 
{
    int n, m;
    cin >> n >> m;

    vector<vector<char>> ret(n, vector<char> (m));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> ret[i][j];

    vector<vector<int>> dp(n + 1, vector<int> (m + 1, 0));

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) + GetScore(ret[i][j]);

    cout << dp[n][m] << endl;
    return 0;
}

逻辑解释：到达 (i,j) 的最大得分，取决于从上方 (i-1,j) 或左方 (i,j-1) 哪个方向过来的得分更高，再加上当前格子的字母得分。所以状态转移方程即为 ： dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]) + GetScore(ret[i][j]);