20161116
brute-force, O(N^5)
직사각형을 잡을때 나무가 "꼭지점이 아닌" 모서리에 올 수 있도록 라인 스위핑을 해 주어야한다.
N = 40 이므로 모든 직사각형을 N^4에 찾아서
각 직사각형 마다 외부를 제거해주고 울타리를 만들 수 있으면 정답 후보에 넣고 break
울타리 길이가 모자라면 모자란 만큼 내부에서 가치가 가장 높은 나무부터 잘라가면서 울타리를 만들 수 있으면 정답 후보에 넣고 break
해준다.
N^5 = 102400000 이므로 빠듯할 것 같지만
적절한 가지치기를 하면 N^4에 가까운 시간 복잡도로 해결 가능하다.
더 가지치기 가능한 부분 :
처음에 외부를 제거할 때 내부, 외부를 미리 구분해두면 좀 더 빨라진다.
#include <iostream> // standard input & output cout cin
#include <cstdio> // scanf printfsssss
#include <vector> // std::vector
#include <algorithm>
#include <string> // std::string
#include <queue> // std::queue
#include <cstring> // memset
#include <set> // std::set
#include <utility> // std::pair, std::make_pair
#include <map>
#include <list>
#include <stack>
#include <deque>
#include <cmath>
#include <climits>
#include <cassert>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef long double ld;
#define mod 1000000007
const char newline = '\n';
ll powmod(ll a, ll b) {ll res=1; a %= mod; assert(b >= 0); for(; b; b >>= 1) {if (b & 1) res = res * a % mod; a = a * a % mod;} return res;}
#define P pair<int, int>
int main(int argc, char **argv)
{
ios_base::sync_with_stdio(false); cin.tie(0);
vector<tuple<int, int, int> > vv;
vector<int> xcor, ycor;
int n;
cin>>n;
for(int i = 0 ; i < n ; i++)
{
int y,x,val;
cin>>y>>x>>val;
vv.push_back(make_tuple(val, y,x));
ycor.push_back(y);
xcor.push_back(x);
}
sort(ycor.begin(), ycor.end());
sort(xcor.begin(), xcor.end());
unique(ycor.begin(), ycor.end());
unique(xcor.begin(), xcor.end());
sort(vv.rbegin(), vv.rend()); // 나무들을 val가 내림차순이 되도록 정렬
// for(auto &i : ycor)
// cout<<i<<' ' ;
// cout<<newline;
// for(auto &i : xcor)
// cout<<i<<' ' ;
// cout<<newline;
int answer = 123456789;
int v,y,x;
int down, up, right, left;
for(int tup = 0 ; tup < ycor.size() ; tup++)
{
for(int tleft = 0 ; tleft < xcor.size() ; tleft++)
{
for(int tdown = ycor.size() - 1 ; tdown >= tup ; tdown--)
{
for(int tright = xcor.size() - 1 ; tright >= tleft ; tright--)
{
left = xcor[tleft];
right = xcor[tright];
up = ycor[tup];
down = ycor[tdown];
int perimeter = 2*((down-up) + (right-left));
int cnt = 0;
int value = 0;
if(perimeter >= answer) continue;
// cout<<left<<' '<<up<< ' ' <<right<<' '<<down<<newline;
// cout<<perimeter<< ' ';
// cout<<answer<<newline;
// cut outer tree
bool valid = true;
for(const tuple<int,int,int> &tt : vv)
{
tie(v,y,x) = tt;
if(y < up || y > down || x < left || x > right)
{
cnt++;
value += v;
if(cnt >= answer) // not valid
{
valid = !valid;
break;
}
}
}
if(!valid) continue;
if(perimeter <= value && cnt < answer)
{
answer = cnt;
continue;
}
// cut inner tree
for(const tuple<int,int,int> &tt : vv)
{
tie(v,y,x) = tt;
if(y >= up && y <= down && x >= left && x <= right)
{
cnt++;
value += v;
if(cnt >= answer) // not valid
{
valid = !valid;
break;
}
if(value >= perimeter)
{
answer = cnt;
break;
}
}
}
}
}
}
}
cout<<answer<<newline;
return 0;
}