题目描述

出题人是一项开采项目的负责人。整个矿坑可以被看成一个 $N×N$ 的方阵，每个格子所代表的区域内有一些有矿，有的没有。

在进行开采之前，出题人只知道哪些格子有矿，而你需要帮他探明所有有矿的格子中的蕴藏量。

你有一个超能力，可以一次性探清 $H×W$ 的矩形中所有格子内的矿物蕴藏量；不过使用一次需要消耗 $max(H,W)$ 的能量。

你需要在完成出题人给你的任务的情况下最小化消耗的能量并将这个数告诉出题人即可。

输入格式

输入文件名为

detection.in

第一行，一个整数 $N$ ，表示方阵的边长 。 接下来 $N$行，每行一个字符串， $N$ 个字符串表示一张地图。其中 T 表示格子内有矿物。

输出格式

一行一个正整数表示答案。

数据范围

对于100%数据，$N\le60$

思路

设$dp_{i,j}$表示从$(1,1)$探测到$(i,j)$所需要的最小代价。我们枚举$1\le i_1 \le i,1\le j_1 \le j$，则由容斥原理，有$dp_{i,j}=min(dp_{i,j},dp_{i_1-1,j}+dp_{i,j_1-1}+C$ 若以$(i_1,j_1)$为左上角，$(i,j)$为右下角的长方形中有需要探测的点，则$C=max(i-i_1+1,j-j_1+1)$，反之则$C=0$。

下面我们来考虑如何快速判断一个长方形内有无需要探测的点。将需要探测的点赋值为1，不需要的赋值为0，再做二维前缀和即可。

以下是代码：

#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;
char map[65][65];
int dp[65][65];
int cnt[65][65];
int main(){
	//freopen("detection2.in","r",stdin);
	//freopen("detection2.out","w",stdout);
	int n;
	cin>>n;
	if(n==1){
		char c;
		cin>>c;
		if(c=='T') cout<<1<<endl;
		else cout<<0<<endl;
		return 0;
	}
	int cnt_t=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			cin>>map[i][j];
			if(map[i][j]=='T'){
				cnt[i][j]=1;
				cnt_t++;
			} 
		} 
	if(cnt_t<=2){
		cout<<cnt_t<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) cnt[i][j]=cnt[i][j-1]+cnt[i-1][j]-cnt[i-1][j-1]+cnt[i][j];
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1;i<=n;i++) dp[i][0]=dp[0][i]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			for(int i1=1;i1<=i;i1++)
				for(int j1=1;j1<=j;j1++){
					bool tflag=1;
					if(dp[i][j]==7) tflag=0;
					int t=cnt[i][j]-cnt[i][j1-1]-cnt[i1-1][j]+cnt[i1-1][j1-1];
					dp[i][j]=min(dp[i][j],dp[i][j1-1]+dp[i1-1][j]-dp[i1-1][j1-1]+(t>0?max(i-i1+1,j-j1+1):0));
					if(i==8 and j==5 and dp[i][j]==7 and tflag){
						cout<<i1<<" "<<j1<<endl;
						cout<<t<<endl;
						cout<<dp[i][j1-1]<<" "<<dp[i1-1][j]<<" "<<dp[i1-1][j1-1]<<" "<<max(i-i1+1,j-j1+1)<<endl;
					} 
				}
		}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) cout<<setw(1)<<dp[i][j];
		cout<<endl;
	} 
	cout<<dp[n][n]<<endl;
}

该代码在原OJ上AC 链接：https://www.xinyoudui.com/contest?courses=685&books=676&pages=19969&fragments=63899&problemId=19036

hack

经过同机房大佬对拍，发现一组可以hack本代码的数据：

10
TOOOOOOOOO
OOOOOOOOOO
OOTTOOTOOO
TOOOOOOOOO
OTOOOOOOOO
OOOOTOOOOO
OOOTOOOTOT
OOTOOOOOOO
OOTOOTOOOO
OOOOOOOOOO

代码输出9，而答案应为10。所以该思路到底有什么问题，希望各位大佬能予以解答。