[题解][洛谷P1174] 打砖块

题目分析

n行m列的砖块，起始有k发子弹。每次可以用一发子弹，打碎某一列当前处于这一列最下面的那块砖，并且得到相应的得分。
某些砖块打碎以后会获得一个砖块。
求最大得分。

题解

可以看出是一道动态规划题。
关键在于如何设计状态。
先考虑砖块打碎不会得到子弹的情况：这个时候可以将同一列的连续多个砖块看作一个物品，其代价是砖块的数量。
预处理后，得到每组各有n个物品，共m组。
此时转换为分组背包问题。
再考虑如何处理获得新子弹的问题：

• 首先，最后一个打碎的砖块一定不会获得子弹，不然可以另外打碎新的砖块。
• 对于通过上述算法得到的分组背包物品代价，减去获得的子弹数量，视为新的代价。
• 设f[i][j][0/1]表示：在i组物品中，使用了j个子弹，且是否已打碎最后一个砖块（0/1）的最大价值。可知答案为f[m][k][1]。

代码

#include<bits/stdc++.h>
#define  int  long long
using namespace std;
const int N=207;
int a[N][N],v[N][N],sum[N][N][2],f[N][N][2];
signed main(){
	int n,m,kk;
	cin>>n>>m>>kk;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;
			cin>>a[i][j]>>c;
			v[i][j]= c=='Y';
		}
	}
	for(int i=1;i<=m;i++){
		int tot=0;
		for(int j=n;j>=1;j--){
			if(v[j][i])sum[i][tot][0]+=a[j][i];
			else{
				++tot;
				sum[i][tot][0]=sum[i][tot-1][0]+a[j][i];
				sum[i][tot][1]=sum[i][tot-1][0]+a[j][i];
			}
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=kk;j++){
			for(int k=0;k<=min(j,n);k++){
				f[i][j][0]=max(f[i][j][0],f[i-1][j-k][0]+sum[i][k][0]);//对于尚未选到最后一个砖块，直接尝试继承i-1并更新。
				if(k)f[i][j][1]=max(f[i][j][1],f[i-1][j-k][0]+sum[i][k][1]);//若要将此时选到的视为最后一个砖块：从尚未选到最后一个砖块处更新
				if(j>k)f[i][j][1]=max(f[i][j][1],f[i-1][j-k][1]+sum[i][k][0]);//将之前选到的视为最后一个砖块：从已经选到最后一个砖块处更新，注意j>k，否则会不足够支付代价。
			}
		}
	}
	cout<<f[m][kk][1]<<endl;
}