TopCoderOpen Algorithm 2014 Round 2A EASY (250pt)
Problem Statement
幅,奥行きのサイズが $1$ で高さ $H_k$ の直方体のブロック($k=1,2,\ldots,16$)が $1$ 個ずつ,合計 $16$ 個ある.
各マスの幅,奥行きのサイズが $1$ の$4$ 行 $4$ 列の盤面の各マスにブロックを置く.
できたブロックから成る物体の表面積の最大値を求める問題.
ブロックの上の面は表面積に含めるが,下の面(テーブルに面する面)は表面積に数えない.
Greedy.
他のブロックと接する面積(消える表面積)を最小化すれば良い.
$4 \times 4$ の盤面を市松模様に塗り分け,その片方に高い方から $8$ 個のブロックを,もう片方に小さい方の $8$ 個のブロックを置く.
大きいブロックを適当においた後,小さいブロックを置いた時に消える表面積を考える.
それは,大きいブロックの置き方に依存せず,置く場所と接するブロックの数と,置くブロックの高さ(の積)に依存する.
よって,接するブロックが多い真ん中には最も小さいブロックを,接する部分の少ない角には,小さい $8$ 個のブロックの中でも大きい物を置くようにする.
大きい方から置く,小さい方から置くとして,すでに置かれているマスの集合を状態としてDPすることもできる(らしい).
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
class SixteenBricks {
public:
int maximumSurface(vector <int> h) {
int i, j, k, n = 16;
int mp[6][6] = {};
int res = 0;
sort(h.begin(), h.end());
k = 0;
mp[2][2] = h[k++];
mp[3][3] = h[k++];
mp[1][3] = h[k++];
mp[2][4] = h[k++];
mp[3][1] = h[k++];
mp[4][2] = h[k++];
mp[1][1] = h[k++];
mp[4][4] = h[k++];
rep(i,4) rep(j,4) if(mp[i+1][j+1]==0) mp[i+1][j+1] = h[k++];
rep(i,4) rep(j,4){
res += 1;
res += max(0, mp[i+1][j+1] - mp[i][j+1]);
res += max(0, mp[i+1][j+1] - mp[i+1][j]);
res += max(0, mp[i+1][j+1] - mp[i+1][j+2]);
res += max(0, mp[i+1][j+1] - mp[i+2][j+1]);
}
return res;
}
}
Current time: 2024年03月29日21時53分05秒
Last modified: 2014年05月18日19時14分47秒 (by laycrs)
Tags: Competitive_Programming TopCoder TopCoderOpen TCO_Algorithm TCO_Algorithm_2014 TCO_Algorithm_2014_2A
トップページに戻る
Logged in as: unknown user (not login)