Pascal(fpc 3.0.2) 解法, 执行用时: 79ms, 内存消耗: 632K, 提交时间: 2019-01-07 18:11:52
program cut;
var
f,g:array[-10..200,-10..200] of longint;
map,map1:array[-10..200,-10..200] of boolean;
i,j,k,n,m,x,y,max:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function jisuan(x,y:longint):longint;
var
i,j,max:longint;
begin
fillchar(f,sizeof(f),0);
fillchar(g,sizeof(g),0);
max:=0;
for i := x to y do
for j :=1 to 2*i-1 do
if map[i,j] then
begin f[i,j]:=1;g[i,j]:=1;end;
for i := y-1 downto x do
for j :=1 to 2*i-1 do
if j mod 2=1 then
if f[i,j]=1 then
if map[i+1,j+1] then
begin
f[i,j]:=min(f[i+1,j],f[i+1,j+2])+1;
if f[i,j]>max then max:=f[i,j];
end;
for i :=x+1 downto y do
for j :=1 to 2*i-1 do
if j mod 2=0 then
if g[i,j]=1 then
if map[i-1,j-1] then
begin
g[i,j]:=min(g[i-1,j-2],g[i-1,j])+1;
if g[i,j]>max then max:=g[i,j];
end;
exit(max);
end;
procedure doit;
var ans1,ans2,i:longint;
begin
for i :=1 to n-1 do
begin
ans1:=jisuan(1,i);
ans2:=jisuan(i+1,n);
if sqr(ans1)+sqr(ans2)>max then
max:=sqr(ans1)+sqr(ans2);
end;
end;
procedure xuan;{把三角形旋转120°}
var
x,y,q,p,i,j:longint;
begin
x:=0;y:=0;
fillchar(map1,sizeof(map1),true);
while y<>2*n-1 do
begin
x:=x+1;y:=0;
p:=n;q:=x*2-1;
while y<>2*x-1 do
begin
y:=y+1;
map1[x,y]:=map[p,q];
if q mod 2=1 then q:=q-1
else begin p:=p-1;q:=q-1;end;
end;
end;
map:=map1;
end;
begin
reset(input);
rewrite(output);
readln(n);
for i := 1 to n do
begin
for j := 1 to 2*n-1 do
map[i,j]:=true;
end;
readln(m);
for i :=1 to m do
begin
readln(x,y);
map[x,y]:=false;
end;
for i :=1 to 3 do
begin
doit;
if i<>3 then
xuan;
end;
writeln(max);
close(input);
close(output);
end.
C++11(clang++ 3.9) 解法, 执行用时: 2ms, 内存消耗: 396K, 提交时间: 2020-08-17 10:19:29
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110;
int n,m;
bool a[N][N];
int data[N][N];
int min1(int x,int y){
return x<y?x:y;
}
int f(int i,int j){
if(data[i][j]!=-1) return data[i][j];
if(i==n){
data[i][j]=1;
return 1;
}
if(!a[i][j]){
data[i][j]=0;
return 0;
}
if(a[i+1][j+1]){
data[i][j]=min1(f(i+1,j),f(i+1,j+2))+1;
return data[i][j];
}else{
data[i][j]=1;
return 1;
}
}
int main(){
//freopen("D.in","r",stdin);
scanf("%d%d",&n,&m);
memset(a,true,sizeof a);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
a[x][y]=false;
}
memset(data,-1,sizeof data);
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<2*i;j++){
int k=f(i,j);
if(k>ans){
ans=k;x=i;y=j;
}
}
}
int s=ans*ans,S=n*n;
if(s+m==S){
printf("%d",s-2*ans+2);
return 0;
}
for(int i=0;i<ans;i++){
for(int j=0;j<2*(i+1);j++){
a[x+i][y+j]=false;
}
}
memset(data,-1,sizeof data);
ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<2*i;j++){
int k=f(i,j);
if(k>ans){
ans=k;x=i;y=j;
}
}
}
ans=ans*ans;
printf("%d\n",ans+s);
return 0;
}
C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 376K, 提交时间: 2020-08-17 09:46:17
#include<cstdio>
#include<cstring>
using namespace std;
const int N=110;
int n,m;
bool a[N][N];
int data[N][N];
int min1(int x,int y){
return x<y?x:y;
}
int f(int i,int j){
if(data[i][j]!=-1) return data[i][j];
if(i==n){
data[i][j]=1;
return 1;
}
if(!a[i][j]){
data[i][j]=0;
return 0;
}
if(a[i+1][j+1]){
data[i][j]=min1(f(i+1,j),f(i+1,j+2))+1;
return data[i][j];
}else{
data[i][j]=1;
return 1;
}
}
int main(){
scanf("%d%d",&n,&m);
memset(a,true,sizeof a);
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
a[x][y]=false;
}
memset(data,-1,sizeof data);
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<2*i;j++){
int k=f(i,j);
if(k>ans){
ans=k;x=i;y=j;
}
}
}
int s=ans*ans,S=n*n;
// for(int i=1;i<=n;i++){
// for(int j=1;j<2*i;j++){
// printf("%d ",data[i][j]);
// }
// puts("");
// }
if(s+m==S){
printf("%d",s-2*ans+2);
return 0;
}
for(int i=0;i<ans;i++){
for(int j=0;j<2*(i+1);j++){
a[x+i][y+j]=false;
}
}
memset(data,-1,sizeof data);
ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<2*i;j++){
int k=f(i,j);
if(k>ans){
ans=k;x=i;y=j;
}
}
}
ans=ans*ans;
printf("%d\n",ans+s);
return 0;
}
