中间m表示在这里一段时间内冒出的鼹鼠的个数,永利官方网站IOI2001的颁奖仪式就要YONG-IN

1910: [Ctsc2002] Award 颁奖典礼

Time Limit: 5 Sec  Memory
Limit: 259 MB
Submit: 183  Solved: 98
[Submit][Status]

bzoj1207【HNOI2004】打鼹鼠

 

Description

IOI2001的颁奖仪式就要YONG-IN
Hall隆重举办。人们在经历了充满梦幻的国际足球联合会世界杯之后变得愈加丰盛情趣。为了使颁奖仪式更具魅力,有人提出在YONG-IN
哈尔l中搭建八个I字型的颁奖台,以此表示音讯学Informatics。构思到竞技的赞助商们或许要在YONG-IN
哈尔l中摆放了相当多显得台,他们可能不愿意移动体现台的职位。你作为IOI二〇〇〇的金牌得主自然地变成了他们求助的靶子。
YONG-IN
哈尔l是四个矩形的网格区域。每个赞助商的显示台都据有了几个单位网格。I型颁奖台将正向搭建,且平行于YONG-IN
哈尔l的边缘。I型颁奖台是由三个矩形相接叠成的,当中上方和人间的矩形的两边必得都高于中间的矩形,不然将被误会成T,
L,
J等字母。比方: 永利官方网站 1 那是五个法定的I型颁奖台,而以下两种情景均非法:永利官方网站 2 希望您编制程序寻觅面积最大的I型颁奖台,使其不掩没任何展现台。

1207: [HNOI2004]打鼹鼠

Time Limit:10 SecMemory Limit:162 MB
Submit:2309Solved:1135
[Submit][Status][Discuss]

Input

先是行包涵五个正整数n, m(1<=n,m<=200),分别代表YONG-IN
哈尔l的矩形网格区域的行数和列数。以下n行每行富含m个数字,非0即1,各类数字描述多少个单位网格,1代表该单位网格存在体现台,0意味着该单位网格子虚乌有展现台。

Description

鼹鼠是生机勃勃种很欢腾挖洞的动物,但每过一定的光阴,它依然喜欢把头探出到本地上来透透气的。依据那个特点阿Q编写了多个打鼹鼠的游艺:在一个n*n的网格中,在一些时刻鼹鼠会在某一个网格探出头来透透气。你能够决定三个机器人来打鼹鼠,假诺i时刻鼹鼠在某些网格中现身,而机器人也高居同一网格的话,那么那几个鼹鼠就能被机器人打死。而机器人每一时时只可以够移动生机勃勃格或停留在原地不动。机器人的活动是指从当前所处的网格移向相邻的网格,即从坐标为(i,j卡塔 尔(英语:State of Qatar)的网格移向(i-1,
j),(i+1,
j),(i,j-1),(i,j+1)两个网格,机器人不可能走出成套n*n的网格。游戏开首时,你能够自便选定机器人的初叶地点。以后你精晓在黄金时代段时间内,鼹鼠现身的时日和地方,希望你编写一个前后相继使机器人在这里风姿罗曼蒂克段时间内打死尽大概多的鼹鼠。

 

Output

仅包罗八个正整数,表示最大的I型颁奖台的面积。倘若不设有法定的I型颁奖台,则输出0。

Input

首先行为n(n<=1000卡塔 尔(英语:State of Qatar),
m(m<=10000卡塔尔,此中m表示在这里风度翩翩段时间内冒出的鼹鼠的个数,接下去的m行每行有七个数据time,x,y表示有三只鼹鼠在游戏伊始后time个时刻,在第x行第y个网格里涌出了叁只鼹鼠。Time按依次增加的顺序给出。注意同不时刻也许现身三只鼹鼠,但相符时刻同大器晚成地点只恐怕现身一只鼹鼠。

 

Sample Input

6 8
1 1 1 1 1 0 0 1
1 0 0 0 0 1 1 1
1 0 0 0 0 0 1 1
1 0 1 0 1 0 1 0
1 0 0 0 0 0 0 1
1 1 0 0 0 1 0 1

Output

仅包涵三个正整数,表示被打死鼹鼠的最高额

 

Sample Output

15

Sample Input

2 2
1 1 1
2 2 2

 

HINT

永利官方网站 3

 题意依旧不行好领悟的,其实也就分为二种情形来转换而已。

【拆解标题】二个  I
 其实正是3个矩形,显明能够用DP做,设f[1..3][i][j][k]意味着到第1..3个矩形截至,第i行,j~k列为底的最大范围。

这么定义大概有歧义,那就比如说贝拉米(Aptamil卡塔尔国下。

永利官方网站 4

 

 

接下来分明的转移:

if(  k~j都是0  )

f[1][i][j][k]=max(f[1][i-1][j][k],0)+k-j+1;

//为何这里max前边有个0?因为要早先化为负的相当大值。那又是干什么?因为不起首化就无法确认保障2号和3号矩形的地点一定有矩形,f[2][1][7][7]将=1
f[2][i][j][k]=max(g2[i-1][j][k],f[2][i-1][j][k])+k-j+1;

//g2[i][j][k]积攒【j,k】闭区间的补集的最优值……←无视那句话,即富含区间【j,k】的最优解
f[3][i][j][k]=max(g1[i-1][j][k],f[3][i-1][j][k])+k-j+1;

//g1[i][j][k]是被【j,k】蕴含的最优解……小编表达不清……不过尔尔水和日常的主张或者咱们都懂

 1 #include<cstring>
 2 #include<cmath>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdio>
 6 #define N 207
 7 #define inf 1000000009
 8 using namespace std;
 9 
10 int n,m,ans;
11 
12 int f[4][N][N][N],s[N][N],x1[N][N][N],x2[N][N][N];
13 
14 int main()
15 {
16     scanf("%d%d",&n,&m);
17     memset(x1,192,sizeof(x1));
18     memset(x2,192,sizeof(x2));
19     memset(f,192,sizeof(f));//先赋值为一个最大值。 
20     for (int i=1;i<=m;i++)
21         for (int j=1;j<=m;j++)
22             f[1][0][i][j]=0;//第零行初始化为0,表示没有长度。 
23     int x;
24     for (int i=1;i<=n;i++)
25         for (int j=1;j<=m;j++)
26             {
27                 scanf("%d",&x);
28                 s[i][j]=s[i][j-1]+x;//处理前缀和。 
29             }
30     for (int i=1;i<=n;i++)
31     {
32         for (int j=1;j<=m;j++)
33             for (int k=j;k<=m;k++)
34             if (s[i][k]-s[i][j-1]==0)//如果这一段都是空地的话。 
35             {
36                 f[1][i][j][k]=max(f[1][i-1][j][k],0)+k-j+1;//如果上一层是有的话,就继续转移。 
37                 f[2][i][j][k]=max(x2[i-1][j][k],f[2][i-1][j][k])+k-j+1;//也是一样的道理,从上一层的最大值来转移。 
38                 f[3][i][j][k]=max(x1[i-1][j][k],f[3][i-1][j][k])+k-j+1;
39                 ans=max(ans,f[3][i][j][k]);//ans每次从当前I型中取最大值。 
40             }
41         for (int l=0;l<=m-1;l++)
42             for (int j=1;j+l<=m;j++)
43             {
44                 int k=j+l;
45                 x1[i][j][k]=max(max(x1[i][j+1][k],x1[i][j][k-1]),f[2][i][j+1][k-1]);//x1数组是用来更新第三块矩阵的,代表了第二号矩阵。 
46             }        
47         for (int l=m-1;l>=0;l--)
48             for (int j=1;j+l<=m;j++)
49             {
50                 int k=j+l;
51                 x2[i][j][k]=max(max(x2[i][j-1][k],x2[i][j][k+1]),f[1][i][j-1][k+1]);//x2数组是用来更新第二块矩阵的,代表了第一号矩阵。 
52             }
53         //x1,x2表示衔接矩阵。    
54     }
55     printf("%d\n",ans);
56 }

 

Sample Output

1

 

HINT

 

 

Source

最长上涨体系

 #include #include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i–)
#define ll long long
#define maxn 10005
using namespace std;
int n,m,ans;
int f[maxn],t[maxn],x[maxn],y[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<‘0’||ch>’9′){if (ch==’-‘) f=-1;ch=getchar();}
while (ch>=’0’&&ch<=’9′){x=x*10+ch-‘0’;ch=getchar();}
return x*f;
}
int main()
{
n=read();m=read();
F(i,1,m) f[i]=1;
F(i,1,m)
{
t[i]=read();x[i]=read();y[i]=read();
F(j,1,i-1) if
(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j])
f[i]=max(f[i],f[j]+1);
}
ans=0;
F(i,1,m) ans=max(ans,f[i]);
printf(“%d\n”,ans);
}
 

 

 

http://www.bkjia.com/cjjc/1099753.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1099753.htmlTechArticlebzoj1207【HNOI2004】打鼹鼠 1207:
[HNOI2004]打鼹鼠 Time Limit:10 SecMemory Limit:162 MB
Submit:2309Solved:1135 [Submit][Status][Discuss] Description
鼹鼠是风度翩翩种很欢跃挖…

相关文章