昨天做了道贪心的题，最近都在做这个，今天先写下这题的报告。
题目：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1230其实如果掌握了动态规划的方法，那对于贪心就只要找到它的贪心性质就可以了，因为贪心也要求最优子结构，找最优子结构的方法和动态规划一样，即要找到对于一个问题，它的最优解包含了其子问题的最优解(对了，前面说要总解动态规划的，一直没总结，这类题的确很多，也很关键)。贪心性质简单讲就是一个全局最优解可以通过局部最优选择来达到，就是步步都选择当前最优的情况。
对于这道题，首先是建模，怎样读入题目的信息，我并没有把整个图都用矩阵表示，而是自建了个数据结构row，其属性包括rid(行号)，left(左边界)，right(右边界)；然后用vector把它们一个个读入的，这样既省了空间也省了时间，再用一个column数组存储每个列所占的墙数。这样的存储就已经满足我的算法了。下面是贪心部分，首先是最优子结构，设S
j 为从第0行到第j行为达满足条件而要删去的最小墙数，那么S
j=S
j-1+N
j 其中N
j为为满足第j列墙数不大于k删去的最小墙数，N
j =C
j - k (when C
j > k ) or N
j = 0; 其中C
j为第为j列当前的墙数(即在前面j-1列删除了墙之后)。下面对N
j 加以说明，显然要使它尽可能的小就要使C
j 尽可能的小，所以在删除第j列之前的删除工作要尽量的删除右边界大的墙，也就是对于第j列选择删除墙时也要选择右边界大的墙删除得到N
j 。
我们来证明这样的S
j具有最优子结构性质，即若S
j最优S
j-1也最优。
假设S
j-1不是最优的，那设存在T<S
j-1，因为根据N
j 的选择规则其大小是一定的，所以T+N
j <S
j-1+N
j =S
j，即存在有比S
j更优的方案，这与S
j最优矛盾，所以若S
j最优S
j-1也最优的。
那么根据N
j 的选择方式就可知其满足贪心性质，每次贪心的选择右边界最大的墙删除保证当前列满足条件。
这样算法就出来了，即从下标为0的列从左到右扫描到下标最大的列，对每一列循环操作至这一列的墙数不大于k，循环中每一次操作找右边界最大的墙删除即可。
这题还有一些小细节：
1.题目可能给出的第一个列坐标比第二个大，要判断下；
2.一行可能有多个墙(这个直接影响了算法，不然会有更简单的贪心方法)。
代码如下：
#include<iostream>
using namespace std;
#include<vector>
struct row{
int rid;
int left;
int right;
};
int column[110];
vector<row> wall;
int main()
{
int c,n,k,count=0;
scanf("%d",&c);
while(c--)
{
count=0;
int maxc=0;
scanf("%d%d",&n,&k);
while(n--)
{
int ux,uy,dx,dy;
scanf("%d%d%d%d",&ux,&uy,&dx,&dy);
if(ux>dx)
{
ux=ux+dx;
dx=ux-2*dx;
dx=(ux+dx)/2;
ux=ux-dx;
}
if(dx>maxc)
maxc=dx;
row temp;
temp.rid=uy;
temp.left=ux;
temp.right=dx;
wall.push_back(temp);
for(int i=ux;i<=dx;i++)
column[i]++;
}
int maxv=1;
for(int i=0;i<=maxc;i++)
{
while(column[i]>k)
{
vector<row>::iterator it=wall.begin();
vector<row>::iterator iter;
maxv=0;
while(it!=wall.end())
{
if((*it).left<=i)
{
if((*it).right>maxv)
{
maxv=(*it).right;
iter=it;
}
}
it++;
}
for(int i=(*iter).left;i<=(*iter).right;i++)
{
column[i]--;
}
wall.erase(iter);
count++;
}
}
printf("%d\n",count);
wall.clear();
memset(column,0,sizeof(column));
}
return 0;
}
posted on 2009-06-02 12:31
tortoisewu 阅读(1991)
评论(0) 编辑 收藏 引用