HDU 4314 드워프 탈출 dp
문제풀이: dp[i][j]는 전 i인 중 j인을 탈출한 후에 남은 우물에서 드워프가 탈출하려면 최소한 한 사람이 필요로 하는 최소 높이가 얼마나 되는지를 의미한다. 분석한 결과 다음과 같다. 탈출한 j인 중 마지막에 탈출한 사람은 반드시ai+bi가 가장 크다. 이렇게 해야만 dp치가 가장 좋은 것을 얻을 수 있다. 먼저 드워프에게ai+bi가 크고 작은 순서에 따라 현재 i인이 탈출할 수 있는지 고려해야 한다.즉 dp[i][j]는 두 가지 상황에서만 얻을 수 있다.
dp[i-1][j]:i 위치의 사람이 탈출하지 않았기 때문에 필요한 높이는 dp[i-1][j]-a[i]이다.
dp[i-1][j-1]: i 위치의 사람이 탈출했습니다. 필요한 높이는 두 가지가 있습니다.
1i의 키와 팔의 길이가 충분하여 이전에 필요한 높이를 이용하여 탈출할 수 있다. 이때 필요한 높이는 dp[i-1][j-1]이다.
2i의 키와 팔의 길이가 크지 않다. 이때 i가 가장 먼저 탈출하기 때문에 필요한 높이는 전 i-1명이 i의 탈출을 도와주고 필요한 높이는 H-sumA[i]-b[i]이다.
상기 두 가지 상황은 모두 만족해야 dp[i][j]를 얻을 수 있기 때문에 최대치를 취해야 한다. 종합적으로 dp방정식을 얻어야 한다. dp[i][j]=MIN(dp[i-1][j]-dwarf[i].a,MAX(dp[i-1][j-1],h-sum[i]-dwarf[i].b)).Sure 오리지널, 전재는 출처를 밝혀 주십시오.
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#define MIN(a , b) ((a) < (b) ? (a) : (b))
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const int inf = 1 << 29;
const int maxn = 2002;
struct D
{
int a,b;
bool operator < (const D &other) const
{
return a + b > other.a + other.b;
}
}dwarf[maxn];
int sum[maxn],dp[maxn][maxn];
int n,h;
void read()
{
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
{
scanf("%d %d",&dwarf[i].a,&dwarf[i].b);
}
scanf("%d",&h);
sort(dwarf + 1 , dwarf + n + 1);
sum[0] = 0;
for(int i=1;i<=n;i++)
{
sum[i] = sum[i-1] + dwarf[i].a;
}
for(int i=0;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
dp[i][j] = inf;
}
}
return;
}
void solve()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
dp[i][j] = MIN(dp[i-1][j] - dwarf[i].a , MAX(dp[i-1][j-1] , h - sum[i] - dwarf[i].b));
}
}
for(int i=n;i>=0;i--)
{
if(dp[n][i] <= 0)
{
printf("%d
",i);
break;
}
}
return;
}
int main()
{
while(~scanf("%d",&n))
{
read();
solve();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스은 접근자 메서드가 있는 속성 모음입니다. 클래스를 명시적으로 작성할 필요 없이. Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다. 각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
