【HDU 7110】:Shooting Bricks 分組背包

傳送門

題意

分析

首先我們可以考慮背包的思想

用 f [ i ] [ j ] f[i][j] f[i][j]表示前 i i i列用了 j j j枚子彈，但是這樣遇到一個問題就是，比如有三行二列，第一列全部都是有獎勵，第二列第一行沒有獎勵，其餘兩行有獎勵，那麼，如果我們先打第二列再打第一列，那麼就要用掉兩顆子彈，如果先打第一列再去打第二列，那麼隻需要用掉兩顆子彈

是以，我們用 f [ i ] [ j ] [ 0 / 1 ] f[i][j][0/1] f[i][j][0/1]表示前 i i i列用了 j j j枚子彈，并且這 i i i列最上面一行是否有非獎勵磚塊

這樣，最後的答案就是 m a x ( f [ m ] [ k ] [ 1 ] , f [ m ] [ k − 1 ] [ 0 ] ) max(f[m][k][1],f[m][k - 1][0]) max(f[m][k][1],f[m][k−1][0])

代碼

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int N = 210;
const ll mod = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a) {
	char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
	while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
int gcd(int a, int b) {return (b > 0) ? gcd(b, a % b) : a;}
int n,m,k;
int a[N][N],b[N][N];
int f[N][N][2];

int main() {
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&k);
		for(int i = n;i;i--)
			for(int j = 1;j <= m;j++){
				char x[2];
				scanf("%d%s",&a[i][j],x);
				b[i][j] = (*x == 'N');
			}
		for(int j = 0;j <= m;j++)
			for(int i = 0;i <= k;i++)
				f[j][i][0] = 0,f[j][i][1] = -INF;
		for(int j = 1;j <= m;j++){
			int res = 0,sum = 0;
			for(int i = 0;i <= k;i++) {
				f[j][i][0] = f[j - 1][i][0];
				f[j][i][1] = f[j - 1][i][1];
			}
			for(int i = 1;i <= n;i++){
				sum += a[i][j];
				res += b[i][j];
				for(int x = k;x >= res;x--){
					f[j][x][0] = max(f[j][x][0],f[j - 1][x - res][0] + sum);
					f[j][x][1] = max(f[j][x][1],f[j - 1][x - res][1] + sum);
					if(b[i][j]){
						f[j][x][1] = max(f[j][x][1],f[j - 1][x - res][0] + sum);
					}
				}
			}
		}
		di(max(f[m][k][1],f[m][k - 1][0]));
	}
	return 0;
}