我用java写的内部数据都过了为什么提交不对啊。。。

package javaTest;

import java.util.Arrays;
import java.util.Scanner;
import java.awt.event.KeyEvent;
import java.io.*;
import java.security.GeneralSecurityException;
import java.util.*;
import java.util.Scanner;

public class Main {

public static final int INF=(int) Double.MAX_VALUE;
public static Vector<Point> point=new Vector<Point>();
public static Vector<Matrix> matrix=new Vector<Matrix>();
public static int k=0;
public static int n=0;
public static int ans=INF;
static class Point
{
public int y;
public int x;
public Point(int x,int y) {
// TODO Auto-generated constructor stub
this.x=x;
this.y=y;
}

}
static class Matrix
{
public int leftx;
public int rightx;
public int lefty;
public int righty;

public Matrix() {
// TODO Auto-generated constructor stub
}

public Matrix(int leftx,int rightx,int lefty,int righty) {
// TODO Auto-generated constructor stub

this.leftx=leftx;
this.rightx=rightx;
this.lefty=lefty;
this.righty=righty;

}

}
public static int getans()
{
int tmp=0;
for(int i=0;i<k;i++)
{

if(matrix.get(i).leftx!=INF)
tmp+=(matrix.get(i).rightx-matrix.get(i).leftx)*(matrix.get(i).righty-matrix.get(i).lefty);

}

return tmp;

}
public static int check( int i,int j)
{
int ok=1;
if(matrix.get(i).leftx==INF||matrix.get(i).lefty==INF||matrix.get(i).rightx==-INF||matrix.get(i).righty==-INF)
ok=0;
if(matrix.get(j).leftx==INF||matrix.get(j).lefty==INF||matrix.get(j).rightx==-INF||matrix.get(j).righty==-INF)
ok=0;
if(matrix.get(i).leftx>matrix.get(j).rightx||matrix.get(i).lefty>matrix.get(j).righty)

ok=0;
if(matrix.get(j).leftx>matrix.get(i).rightx||matrix.get(j).lefty>matrix.get(i).righty)
ok=0;

if(ok==1)
return 1;
else
return 0;

}
public static int finalcheck()
{

int ok=1;
for(int i=0;i<k;i++)
{ for(int j=i+1;j<k;j++)
{ if(check(i, j)==1)
ok=0;
}
}
return ok;
}
public static void DFS(int now)
{

if(now==n)
{
ans=getans();
return;

}

for(int i=0;i<k;i++)
{

int leftx=matrix.get(i).leftx;
int rightx=matrix.get(i).rightx;
int lefty=matrix.get(i).lefty;
int righty=matrix.get(i).righty;
Matrix tmp=new Matrix(leftx, rightx, lefty, righty);
if(matrix.get(i).leftx>point.get(now).x)
matrix.get(i).leftx=point.get(now).x;
if(matrix.get(i).lefty>point.get(now).y)
matrix.get(i).lefty=point.get(now).y;
if(matrix.get(i).rightx<point.get(now).x)
matrix.get(i).rightx=point.get(now).x;
if(matrix.get(i).righty<point.get(now).y)
matrix.get(i).righty=point.get(now).y;

if(finalcheck()==1&&getans()<ans)
DFS(now+1);

matrix.set(i, tmp);

}

}

public static void main(String[] args) {
Scanner cin=new Scanner(System.in);

n=cin.nextInt();
k=cin.nextInt();
for(int i=0;i<n;i++)
{
int x=cin.nextInt();
int y=cin.nextInt();
Point tmpPoint=new Point(x, y);
point.add(tmpPoint);
}
for(int i=0;i<k;i++)
{

Matrix tmpMatrix=new Matrix();
tmpMatrix.leftx=INF;
tmpMatrix.lefty=INF;
tmpMatrix.rightx=-INF;
tmpMatrix.righty=-INF;
matrix.add(tmpMatrix);

}

DFS(0);
System.out.println(ans);

}

}

5 条评论

  • 1

信息

ID
1126
难度
4
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
1386
已通过
551
通过率
40%
被复制
11
上传者