POJ. - 1017 욕심.
4231 단어 탐욕스럽다
그리고 POJ는 왜 그런지 몰라서 며칠 동안 터졌는데 이 문제를 오랜만에 제출했다.
아이디어:
6*6:하나에 상자 하나 독점
5*5:하나는 하나의 상자를 독점해야 하며, 다 넣으면 11개를 더 넣을 수 있다.
4*4: 하나는 하나의 상자를 독점해야 하며, 다 넣은 후에 5개의 2*2(먼저 큰 것을 꽉 끼게 놓고)를 넣을 수 있다. 그리고 여유가 있으면 1*1로 채울 수 있다.
3*3: 이건 좀 귀찮아요. 상황을 분리해서 생각해야 해요.
2*2와 1*1은 위의 사고방식과 같다.
코드가 간결하지 않으니 다들 아쉬운 대로 보세요. 어쨌든 ac입니다.
#include
using namespace std;
int a[7];
int main()
{
while (!cin.eof())
{
int sum = 0;
for (int i = 1; i <= 6; i++) {cin >> a[i]; sum += a[i];}
if (!sum) break;
int ans = 0;
if (a[6]) ans += a[6];
if (a[5])
{
ans += a[5];
int area = a[5] * 11;
a[1] = (a[1] - area) <= 0 ? 0 : (a[1] - area);
}
if (a[4])
{
ans += a[4];
int area = 20 * a[4];
if (a[2])
{
if (area - a[2] * 4 <= 0)
{
a[2] -= (area / 4);
area = 0;
}
else
{
area -= a[2] * 4;
a[2] = 0;
}
}
if (area && a[1])
{
if (area - a[1] <= 0) a[1] -= area;
else a[1] = 0;
}
}
if (a[3])
{
ans += (a[3] / 4);
a[3] %= 4; //3*3
if (a[3]) {
int area = 36 - (9 * a[3]);
ans += 1;
if (a[3] == 1)
{
area = 27;
if (a[2])
{
if (a[2] <= 5)
{
area -= (4 * a[2]);
a[2] = 0;
}
else
{
area -= 20;
a[2] -= 5;
}
}
if (area)
{
if (a[1])
{
if (a[1] <= area) a[1] = 0;
else a[1] -= area;
}
}
}
else if (a[3] == 2)
{
area = 18;
if (a[2])
{
if (a[2] <= 3)
{
area -= (4 * a[2]);
a[2] = 0;
}
else
{
area -= 12;
a[2] -= 3;
}
}
if (area)
{
if (a[1] >= area) a[1] -= area;
else a[1] = 0;
}
}
else if (a[3] == 3)
{
if (a[2])
{
a[2] -= 1;
if (a[1])
{
if (a[1] <= 5) a[1] = 0;
else a[1] -= 5;
}
}
else
{
if (a[1])
{
if (a[1] <= 9) a[1] = 0;
else a[1] -= 9;
}
}
}
}
}
if (a[2])
{
ans += (a[2] / 9);
a[2] %= 9;
if (a[2])
{
int area = 36 - (4 * a[2]);
a[1] = (a[1] - area <= 0) ? 0 : (a[1] - area);
ans++;
}
}
if (a[1])
{
ans += (a[1] % 36 == 0) ? (a[1] / 36) : (a[1] / 36) + 1;
}
cout << ans << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[noip2013] 꽃장인DP||욕심화공의 동채에 한 줄의 꽃을 심었는데, 꽃마다 모두 자신의 높이가 있다.꽃은 자랄수록 커지고 비좁아진다.동동은 이 줄의 일부 꽃을 옮기고 나머지는 제자리에 남겨 남은 꽃이 자랄 수 있는 공간을 마련하기로 했다. 또한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.