打砖块（洛谷）

hi，大家好啊！

（回眸一笑百媚生^-^）

直接不上表情包了，改文字

一道 提高+/省选− 的题，还是有点挑战性的

但不急，上代码

（作者在破200粉）

#include <algorithm>
#include <iostream>
#define int long long
using namespace std;

const int MAXN = 1003;

int f[MAXN][MAXN];
char c[MAXN][MAXN];

int dp1[MAXN][MAXN]; //dp_i,j: 考虑前i列，花费j颗子弹，最后一颗子弹打在这一列的最高分数
int dp2[MAXN][MAXN]; //dp_i,j: 考虑前i列，花费j颗子弹，最后一颗子弹不打在这一列的最高分数
int sum1[MAXN][MAXN], sum2[MAXN][MAXN]; // sum：分数的前缀和

int n, m, k;
signed main() {
    // 数据输入
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> f[i][j] >> c[i][j];
        }
    }
    // 初始化sum
    for (int i = 1; i <= m; i++) {
        int cnt = 0;
        for (int j = n; j > 0; j--) {
            if (c[j][i] == 'Y') {
                sum1[i][cnt] += f[j][i]; // 这一列可以预支
            } else {
                cnt++;
                sum1[i][cnt] = sum2[i][cnt] = sum1[i][cnt - 1] + f[j][i];
            }
        }
    }
    // dp
    for (int j = 1; j <= m; j++) { // 列数
        for (int i = 0; i <= k; i++) { // 消耗的总子弹数
            for (int l = 0; l <= min(n, i); l++) { // 在当前列消耗的子弹数
                dp1[j][i] = max(dp1[j][i], dp1[j - 1][i - l] + sum1[j][l]); // 如果当前这一列不是最后打到的，就可以无脑预支
                if (l != 0) dp2[j][i] = max(dp2[j][i], dp1[j - 1][i - l] + sum2[j][l]); // 不预支的情况
                if (l < i) dp2[j][i] = max(dp2[j][i], dp2[j - 1][i - l] + sum1[j][l]); // 一定可以预支的情况
            }
        }
    }
    cout << dp2[m][k] << '\n';
    return 0;
}
一定要关注本喵哦!!!!!!!!!