Luogu p1174

题解

解

贪心 + dp

对于最下面一行是 $Y$ 的砖块可以免费打掉
对于 $Y$ 与 $N$ 交叉的地方，now[] 存储将 $N$ 上面全部的 $Y$ 的总分累积在 $N$ 的位置, res[] 存储每一列的前缀和，最后 now[] 要加上 ret[],表示该点以下所有的点都选了，并且该点上面连续的免费砖块也都打掉了
预处理 ci[i][j] 表示在 i 列打掉前 j 个砖块所需要的子弹。
分组背包思想: dp[j][i] 表示前j列总共耗费i个子弹,且之后不用”借”子弹，dp[i][j][1] 表示之后还要”借“子弹，所能得到的最大分数（“借”的意思：比如第一列是 2 Y 2 N 且N必须先打掉，那么 dp[1][1][0]=2,dp[1][1][1]=4），答案即为 dp[m][k][0].
状态转移方程： dp[j][k][0]=max(dp[j][k][0],max(dp[j-1][k-ci[j][i]][1],dp[j-1][k-ci[j][i]][0])+res[j][i]);
dp[j][k][0]=max(dp[j][k][0],dp[j-1][k-ci[j][i]][0]+now[j][i]);
dp[j][k][1]=max(dp[j][k][1],dp[j-1][k-ci[j][i]][1]+now[j][i]);
初始化： for(j=0;j<=m;j++) dp[j][0][0]=-inf;

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define M(a) memset(a, 0, sizeof a)
using namespace std;
const int N = 205;
int n, m, p, ans;
char ch;
int a[N][N], whe[N], res[N][N];
int dp[N][N][2], ci[N][N], now[N][N];  //0:不需要借，1:需要借
bool b[N][N];
int main() {
    scanf("%d%d%d",&n,&m,&p);
    if(p == 0) {printf("0\n"); return 0;}
    for(int i = n; i >= 1; i --)
        for(int j = 1; j <= m; j ++) {
            scanf("%d", &a[i][j]);
            cin >> ch;
            if(ch == 'Y') b[i][j] = 1;
        }
    for(int j = 1; j <= m; j ++)
        for(int i = 1; i <= n; i ++) {
            if(!b[i][j]) {whe[j] = i; break;}
            ans += a[i][j];
        }
    for(int j = 1; j <= m; j ++)
        for(int i = whe[j]; i <= n; i ++)
            res[j][i] = res[j][i - 1] + a[i][j];
    for(int j = 1; j <= m; j ++)
        for(int i = whe[j]; i <= n; i ++)
            now[j][i] = res[j][i];
    for(int j = 1; j <= m; j ++) {
        ci[j][whe[j]] = 1;
        for(int i = whe[j]; i <= n; i ++) {
            int tmp = i;
            while(b[i + 1][j]) i ++;
            now[j][tmp] += res[j][i] - res[j][tmp];
            ci[j][i + 1] = ci[j][tmp] + 1;
        }
    }
    for(int j = 0; j <= m; j ++) dp[j][0][0] = -1e8;
    for(int j = 1; j <= m; j ++)
        for(int k = 1; k <= p; k ++) {
            dp[j][k][0] = max(dp[j][k][0], dp[j - 1][k][0]);
            dp[j][k][1] = max(dp[j][k][1], dp[j - 1][k][1]);
            for(int i = whe[j]; i <= n; i ++)
                if(!b[i][j] && k >= ci[j][i]) {
                    dp[j][k][0] = max(dp[j][k][0], max(dp[j - 1][k - ci[j][i]][1], dp[j - 1][k - ci[j][i]][0]) + res[j][i]);
                    dp[j][k][0] = max(dp[j][k][0], dp[j - 1][k - ci[j][i]][0] + now[j][i]);
                    dp[j][k][1] = max(dp[j][k][1], dp[j - 1][k - ci[j][i]][1] + now[j][i]);
                }
        }
    printf("%d\n",dp[m][p][0] + ans);
    return 0;
}

参考

参考