USACO Section 1.4 packrec-あまり書きにくい検索水題
私もテーマを間違えました.4つのブロックを任意に配置して最小のマトリクスを放出するかと思ったら...後で気づいたのも6つの状況...テーマが与えた6つは...出力もちょっと気持ち悪い..最小面積を先に出力..各長方形の長さと幅を出力します.矩形ごとに出力するには短辺を出力してから長辺を出力します...すべてのマトリクスの順序は、短辺が最も短いものを先に出力します.短辺が等しい出力長辺が短い...次の順に出力マトリクスを繰り返さない...
私の方法はまず4つのマトリクス(それが90度かそのままどちらに対応しているか)を列挙することです...与えられた6つのモジュールにも各マトリクスに番号を付けます~~そして挙げられていない4つのマトリクスと6つのモジュールを列挙したマトリクスの番号を対応させます...最小面積の...上位5つがいいですが...6つ目は気をつけて...いくつかの条件でカードを...
Program:
私の方法はまず4つのマトリクス(それが90度かそのままどちらに対応しているか)を列挙することです...与えられた6つのモジュールにも各マトリクスに番号を付けます~~そして挙げられていない4つのマトリクスと6つのモジュールを列挙したマトリクスの番号を対応させます...最小面積の...上位5つがいいですが...6つ目は気をつけて...いくつかの条件でカードを...
Program:
/*
ID: zzyzzy12
LANG: C++
TASK: packrec
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define oo 2000000000
using namespace std;
struct node
{
int x,y;
}a[5],s[5],ansa[3001];
int i,ans,ansnum;
bool used[5];
void update(int s,int x,int y)
{
if (s==ans)
{
ansnum++;
if (x<y)
{
ansa[ansnum].x=x;
ansa[ansnum].y=y;
}else
{
ansa[ansnum].x=y;
ansa[ansnum].y=x;
}
}else
if (s<ans)
{
ans=s;
ansnum=1;
if (x<y)
{
ansa[ansnum].x=x;
ansa[ansnum].y=y;
}else
{
ansa[ansnum].x=y;
ansa[ansnum].y=x;
}
}
return;
}
void search(int k)
{
int i;
if (k==5)
{
int x,y;
x=s[1].x+s[2].x+s[3].x+s[4].x;
y=max(max(max(s[1].y,s[2].y),s[3].y),s[4].y);
update(x*y,x,y); ///---------------1
x=max(s[1].x+s[2].x+s[3].x,s[4].x);
y=max(max(s[1].y,s[2].y),s[3].y)+s[4].y;
update(x*y,x,y); ///---------------2
x=max(s[1].x+s[2].x,s[3].x)+s[4].x;
y=max(max(s[1].y,s[2].y)+s[3].y,s[4].y);
update(x*y,x,y); ///---------------3
if (s[1].x<=s[3].x)
{
x=s[2].x+s[3].x+s[4].x;
y=max(max(s[1].y+s[3].y,s[2].y),s[4].y);
update(x*y,x,y); ///---------------4
}
if (s[1].x<=s[2].x)
{
x=s[2].x+s[3].x+s[4].x;
y=max(max(s[1].y+s[2].y,s[3].y),s[4].y);
update(x*y,x,y); ///---------------5
}
if (s[1].x+s[2].x<=s[3].x+s[4].x && s[3].y<=s[4].y && s[1].x<=s[3].x)
{
x=s[3].x+s[4].x;
y=max(s[1].y+s[3].y,s[2].y+s[4].y);
update(x*y,x,y); ///---------------6
}
return ;
}
for (i=1;i<=4;i++)
if (!used[i])
{
used[i]=true;
s[k]=a[i];
search(k+1);
s[k].x=a[i].y; s[k].y=a[i].x;
search(k+1);
used[i]=false;
}
}
bool cmp(node a,node b)
{
if (a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
int main()
{
freopen("packrec.in","r",stdin);
freopen("packrec.out","w",stdout);
for (i=1;i<=4;i++) scanf("%d%d",&a[i].x,&a[i].y);
ans=oo;
memset(used,false,sizeof(used));
search(1);
printf("%d
",ans);
sort(ansa+1,ansa+1+ansnum,cmp);
printf("%d %d
",ansa[1].x,ansa[1].y);
for (i=2;i<=ansnum;i++)
if (ansa[i].x!=ansa[i-1].x || ansa[i].y!=ansa[i-1].y)
printf("%d %d
",ansa[i].x,ansa[i].y);
return 0;
}