2014
11-29

# City Planning

After many years, the buildings in HDU has become very old. It need to rebuild the buildings now. So Mr dragon (the president of HDU’s logistics department ) ask Mr Wan (a very famous engineer) for help.
Mr Wan only draw one building on a construction design drawings(all the buildings are rectangle and each edge of buildings’ is paraller or perpendicular to others buildings’ edge ). And total draw n drawings (all the drawings have same width and length . And bottomleft point is (0, 0)). Due to possible overlap of conditions, so when they build a new building, they should to remove all the overlapping part of it. And for each building, HDU have a jury evaluate the value per unit area. Now Mr dragon want to know how to arrange the order of build these buildings can make the highest value.

The first line of input is a number T which indicate the number of cases . (1 < T < 3000);
Each test case will begin with a single line containing a single integer n (where 1 <= n <= 20).
Next n line will contain five integers x1, y1, x2, y2 ,value . x1,y1 is bottomleft point and x2,y2 is topright point , value is the value of the buildings’ unit area.((0 <= x1, y1, x2, y2 <= 10000) (x1 < x2, && y1 < y2) (1 <= value <= 22)

The first line of input is a number T which indicate the number of cases . (1 < T < 3000);
Each test case will begin with a single line containing a single integer n (where 1 <= n <= 20).
Next n line will contain five integers x1, y1, x2, y2 ,value . x1,y1 is bottomleft point and x2,y2 is topright point , value is the value of the buildings’ unit area.((0 <= x1, y1, x2, y2 <= 10000) (x1 < x2, && y1 < y2) (1 <= value <= 22)

1
3
1 1 10 10 4
4 4 15 5 5
7 8 20 30 6

Case 1: 2047

Problem 3634 62MS 224K

#include<iostream>
#include<set>
using namespace std;
struct rect{
int x1,y1,x2,y2,v;
}r[22];
set<int> col[2];
int map[50][50],xcol[50],ycol[50],xnum,ynum;
int cmp(const void *a,const void *b)
{
struct rect *aa=(struct rect *)a;
struct rect *bb=(struct rect *)b;
return bb->v -aa->v;
}
int findx(int a)
{
for(int i=0;i<xnum;i++)
if(a==xcol[i])
return i;
}
int findy(int a)
{
for(int i=0;i<ynum;i++)
if(a==ycol[i])
return i;
}
int main()
{
int cas,ca,n,i,j,k;
__int64 ans;
int sx,sy,ex,ey;
scanf("%d",&cas);
for(ca=1;ca<=cas;ca++)
{
col[0].clear();
col[1].clear();
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d%d%d%d",&r[i].x1,&r[i].y1,&r[i].x2,&r[i].y2,&r[i].v);
col[0].insert(r[i].x1); col[0].insert(r[i].x2);
col[1].insert(r[i].y1); col[1].insert(r[i].y2);
}
qsort(r,n,sizeof(r[0]),cmp);
memset(map,0,sizeof(map));
xnum=ynum=0;
set<int>::iterator it;
for(it=col[0].begin();it!=col[0].end();it++)
xcol[xnum++]=*it;
for(it=col[1].begin();it!=col[1].end();it++)
ycol[ynum++]=*it;
/*for(i=0;i<xnum;i++)
printf("%d ",xcol[i]);
puts("");
for(i=0;i<ynum;i++)
printf("%d ",ycol[i]);
puts("");*/

printf("Case %d: ",ca);
ans=0;
for(i=0;i<n;i++)
{
sx=findx(r[i].x1);  ex=findx(r[i].x2);
sy=findy(r[i].y1);  ey=findy(r[i].y2);
//printf("%d %d %d %d \n",sx,xcol[sx],sy,ycol[sy]);
//printf("%d %d %d %d \n",ex,xcol[ex],ey,ycol[ey]);
//printf("%lld\n",(__int64)(r[i].v));
for(j=sx;j<ex;j++)
{
for(k=sy;k<ey;k++){
if(map[j][k]==0)
{
map[j][k]=1;
ans+=(__int64)(xcol[j+1]-xcol[j])*(__int64)(ycol[k+1]-ycol[k])*(__int64)(r[i].v);
//printf("//%d %d %d %d\n",(xcol[j+1]-xcol[j]),(ycol[k+1]-ycol[k]),(r[i].v),ans);
}
}
}
}
printf("%I64d\n",ans);
}
return 0;
}

昨天比赛做的是多校（十九），悲剧收场！提一下每题的大致意思吧，以后也好回忆……

3632 决斗问题 DP

3635 并查集 最简单的一题

3636 最优搜索

3637 在区间内找一个分子分母和最小的分数 数论

3638 应该也用搜索解决吧 怪兽的视野会移动 咬笔杆……

3639 老鹰捉小鸡 图论连通问题

1. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

2. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false