艺术馆的火灾
Fire of the Art Gallery
IOI2000 National Training Team Originals
Author: 张辰
背景描述
这幢古老的建筑是一个艺术馆，它珍藏着上百件绘画、雕塑以及其他艺术品，就连建筑本身也是一件艺术。但是，岁月并不在乎它的精致与美丽，时光在渐渐剥夺着这幢木屋的生命。终于，在一个月色昏暗的夜晚，它着火了。
艺术馆是一幢两层的小楼，每一层有N个房间，每个房间中收藏的艺术品的价值都可以用一个正整数来表示。下面是一个N=4的例子。
在这个例子中，二层楼的第四个房间中艺术品的价值最大，为60。而一层楼的第四个房间中艺术品的价值仅为20。
在消防队员火速赶到的时候，火势已经蔓延了整个建筑，消防队员们观察每个房间中的火势，将它们分别用一个正整数来表示。在上面的例子中，各房间中的火势可能如下。
你可以看到，二层楼的第四个房间中火势最强，为70。而一层楼的第三个房间中火势较弱，为20。
由于火情紧急，消防队员们准备使用一种新型的灭火器。这种灭火器只能发射K次，每次发射将覆盖一个矩形的区域（矩形的高度可以是1也可以是2）。它的威力巨大，所到之处不但火焰会被扑灭，就连同在一处的艺术品也难以幸免。因此，如何善用这种灭火器成了最大的问题。
一个例子：如果灭火器的一次发射覆盖了下图阴影所示的2×2矩形区域，那么这四个房间的火势和艺术品价值都将成为0。
任务说明
给出艺术馆每层的房间数N和灭火器的发射次数K，以及每个房间中艺术品的价值和火势，你需要决定灭火器每次应该怎样发射（也可以不发射），才能将这次火灾的损失降到最低限度。这个损失用你所摧毁的艺术品的总价值，加上剩余的火势总值（这些火焰将需要消防队员们亲身去扑灭）来衡量。
输入数据
输入文件的第一行有两个整数N（1 <= N <= 100）、K（1 <= K <= 10），分别表示艺术馆中每层的房间数和灭火器的发射次数。
接下来的两行每行有N个整数，其中第4-i行的第j个整数Vi,j表示的是第i层第j个房间中艺术品的价值（1 <= i <= 2，1 <= j <= N，1 <= Vi,j <= 10000）。
再接下来的两行每行也有N个整数，其中第6-i行的第j个整数Fi,j表示的是第i层第j个房间中的火势（1 <= i <= 2，1 <= j <= N，1 <= Fi,j <= 10000）。
输出数据
你的输出文件应该有K行，每行有四个整数L1、R1、L2、R2，表示你的灭火器的一次行动。如果灭火器这次不发射，那么这四个整数都为0；否则这次发射所覆盖的矩形区域的左下角是第L1层的第R1个房间，右上角是第L2层的第R2个房间。
注意：你的每次发射所覆盖的矩形区域必须位于小楼之内，并且矩形的面积至少为0。即1 <= L1 <= L2 <= 2，1 <= R1 <= R2 <= N。
输入输出样例
| INPUT.TXT | OUTPUT.TXT | 样例图示 |
| 4 2
40 50 30 60 30 30 40 20 50 40 50 70 40 50 20 30 |
1 1 1 2
2 3 2 4 |
摧毁艺术品：30+60+30+30=150 剩余火势：50+40+20+30=140 最小损失：150+140=290 |
评分标准
每个测试点都有一定的时间限制。你的程序只有在规定的时限内输出解，并且按照你的方案来发射灭火器可以将损失降到最小，你才会得到相应测试点的分值；否则这个测试点不得分。
注意：本题的解不一定是唯一的。即对于一个测试数据，可能有多种发射灭火器的方案都可以使损失达到最小。在这种情况下，你只要输出最优方案中的任意一种即可。
解题报告
自己独立做出来的好有成就感啊……^_^
做这题的过程还相当传奇。话说那天生物课没拿书，直接被老师赶出去到物理办公室门口站着。岂知那里却安静、光线明亮，清风吹拂，透过窗口可以看见墙上大片翠绿的藤蔓植物在风中生起层层波浪，让人心旷神怡，真是个绝佳的自习的所在。当时手里也没书，没事干，就想起了这道本来一看来源就已经准备直接看题解的题目，和老师要了纸笔，想啊想啊就把这题搞出来了。-_-|||
不扯了，下面说说这题的做法（和官方解法不太一样~）。
这题的模型可以看成是一个2*N的矩形表格中每格存有有序数对(V,F)，现在要从表格中选出一些格子，要求：
1.（选出格子中的V）+（未选中格子中的F）值最小；
2.这些格子能组成的最少完整矩形个数不大于定值K。
在第2个要求中我们强调“最少”和“完整”的矩形，这样才能得到最优解。因此，我们可以设法求出一种满足条件的格子选择，然后再按照最少原则用贪心算法划分矩形，且规定划分得到的矩形互不相交（因为相交时得到的解一定不优于此）。以样例数据为例，先选出(1,1)，(1,2)，(2,3)，(2,4)四个格子，然后再把它们组合成(1,1,1,2)和(2,3,2,4)两个完整矩形。这已经是这四个格子所能组成的最少矩形数目了。（下文中无特殊说明，提到的“矩形”都指满足“最少”和“完整”要求的。）
由于表格的高已经确定为2这个很小的值，我们可以根据每一列的损失数来划分阶段。我们用(i,j,k)来表示一个状态。其中i表示当前状态为第i列，用于阶段划分；k表示此次决策前已经得到的矩形个数，用以在状态转移时限制矩形的个数；j表示要决策列的前一列中的灭火器使用情况，用于在状态转移时更新矩形的数目（后面我们可以看到当前列的决策是否导致新矩形的产生完全取决于前一列的灭火器使用情况）。
选择不同的递推方向会导致不同的状态定义和转移方程。这里我们选择顺推，因为每次决策都会唯一对应一个状态后继，这样转移方程写起来会简单许多。
我们的状态定义为：dp(i,j,k)表示前i列已经有k个矩形、第i列的状态为j之后还能获得的最小损失。转移方程为：dp(i,j,k)=min{dp(i+1,jj,kk)+loss(i+1,jj)}。其中jj表示决策第i+1行灭火器的使用情况。kk为因此得到的矩形数目，即若决策jj导致了矩形个数的增加，则kk=k+1，否则kk=k。loss(i,j)为第i列灭火器使用情况为j时的损失。
每一列的灭火器使用情况（j的取值）有4种：0.楼上楼下都不使用灭火器；1.楼上使用；2.楼下使用；3.上下都用。如果我们画两列格子看看，就会发现矩形数目不增加当且仅当jj=0或j==jj。这样我们就可以通过转移方程求出解dp(0,0,0)。
——但是等等！
这就是我第一次写时出现的疏忽（这让我第一次WA了4个点并调试了整整一个晚上）。我们没有注意到当j=3,jj=1（或2，这里以1为例）时可能有以下两种情况：
其中前一种如我们所想，jj决策导致了矩形数目的增加，但是后一种情况却不是这样。虽然j=3，jj=1，满足矩形数目增加的条件，但是矩形数目实际并没有增加。这是由于更早些的决策已经使第i行的上下两层分属两个矩形。因此我们需要为上下都使用的决策留出两个j值以示区别。这部分细节请看代码。
这样得到的状态定义和转移方程明显满足最有子结构和无后效性。我们可以据此求出最小损失。
这道题并不要求输出最小损失，而是要求输出灭火器每次使用的覆盖范围。这我们就需要构造最优解。我的方法很朴素。在dp过程中维护一个数组build[i][j][k]，其值为状态(i,j,k)做出的最优决策jj。dp结束后，我们就可以递归地在一个bool数组上标记出那些使用了灭火器的格子。最后用贪心（细节见代码）把它们组合成矩形输出，这样问题就解决了。
这个算法思路比较简单，编程复杂度与官方解相当。至于时空复杂度，由于我没有系统学习过相关理论，不好乱说，ms是空间复杂度比官方解高，但是时间复杂度比官方解低？
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
ifstream fin("Input.txt");
ofstream fout("Output.txt");
int room_n,shoot_k,v[3][101],f[3][101];
/*dp(memoization)部分*/
int dp[101][5][11];//[i][j][k]:前i列已经最少有k个完整矩形、第i列的状态为j之后还能获得的最小损失
bool checked[101][5][11];
int memo(int i,int j, int k);
int loss(int i, int j); //memo调用的子过程，返回第i行决策为j时的净损失
/*最优解的构造部分*/
int build[101][5][11]; //记录(i,j,k)状态下要得到最优解，i+1列的状态
bool room[3][101];
void paint(int i, int j, int k);//在room中标出状态(i,j,k)后的灭火器使用情况
/*最优解的输出部分*/
int counter;//记录发射次数
void output(int i); //输出矩形
int main()
{
/*输入部分*/
fin >> room_n >> shoot_k;
for(int i=2;i>=1;i--)
for(int j=1;j<=room_n;j++)
fin >> v[i][j];
for(int i=2;i>=1;i--)
for(int j=1;j<=room_n;j++)
fin >> f[i][j];
/*计算部分*/
unsigned min_loss=memo(0,0,0);
paint(0,0,0);
/*输出部分*/
for(int i=1;i<=room_n;i++) output(i);
for(int j=shoot_k-counter;j>=1;j--)
fout << "0 0 0 0\n";
return 0;
}
//
int memo(int i,int j, int k)
{
if(checked[i][j][k]) return dp[i][j][k];
if(i==room_n) return 0;
dp[i][j][k]=INT_MAX;
for(int jj=0,kk,ans;jj<=3;jj++) //枚举第i+1行状态
{
if(jj==3&&(j==4||j==1||j==2)) jj++; //上下都用时的状态修正
kk=k+!(jj==0||jj==j||j==4);
if(kk<=shoot_k)
ans=memo(i+1,jj,kk)+loss(i+1,jj);
else ans=INT_MAX;
if(dp[i][j][k]>ans)
{
dp[i][j][k]=ans;
build[i][j][k]=jj;
}
}
assert(dp[i][j][k]<INT_MAX);
checked[i][j][k]=true;
return dp[i][j][k];
}
int loss(int i, int j)
{
/*状态j的定义:
0：上层下层都不使用灭火器；
1：上使用；2：下使用；3，4：上下都用
其中3表示与此列相连的使用灭火器的房间最少组成1个完整矩形
4表示与此列相连的使用灭火器的房间已经最少组成2个完整矩形*/
switch(j)
{
case 0:
return (f[1][i]+f[2][i]); //上下都不用
case 1:
return(v[2][i]+f[1][i]); //上用
case 2:
return(v[1][i]+f[2][i]); //下用
case 3: //上下都用
case 4:
return(v[1][i]+v[2][i]);
}
assert(0);
}
//
void paint(int i, int j, int k)
{
if(i==room_n) return;
assert(checked[i][j][k]);
int jj=build[i][j][k];
int kk=k+!(jj==0||jj==j||j==4);
switch(jj)
{
case 0:
break; //上下都不用
case 1:
room[2][i+1]=1; break; //上用
case 2:
room[1][i+1]=1; break; //下用
case 3:
case 4:
room[1][i+1]=room[2][i+1]=true; break; //上下都用
default:
assert(0);
}
paint(i+1,jj,kk);
}
//
void output(int i)
{
counter++;
int ii;
if(room[2][i]&&!room[1][i]) //上用
{
fout << 2 << ' ' << i << ' ';
for(ii=i;ii<=room_n&&room[2][ii];ii++) room[2][ii]=0;
fout << 2 << ' ' << ii-1 << endl;
}
else if(room[1][i]&&!room[2][i]) //下用
{
fout << 1 << ' ' << i << ' ';
for(ii=i;ii<=room_n&&room[1][ii];ii++) room[1][ii]=0;
fout << 1 << ' ' << ii-1 << endl;
}
else if(room[1][i]&&room[2][i]) //上下都用
{
fout << 1 << ' ' << i << ' ';
for(ii=i;ii<=room_n&&room[1][ii]&&room[2][ii];ii++) room[1][ii]=room[2][ii]=0;
fout << 2 << ' ' << ii-1 << endl;
}
else counter--; //上下都不用
}
//
可能你对下面的文章也感兴趣：
