uva 10934 - Dropping water balloons(dp)
제목의 대의: k와 n을 제시하면 k개의 같은 수구가 있고 n의 높이가 있는 건물이 있다는 뜻이다. 그리고 수구가 어느 층에서 떨어지면 깨진다. 적어도 몇 번은 잃어버려야 이 높이를 측정할 수 있다고 묻는다.
문제 풀이 방법: 2점을 말하는 것을 쉽게 생각할 수 있지만 2점을 주의하면 반드시 가장 좋은 것은 아니다. 수구의 수량이 제한되어 있기 때문에 깨지지 않으면 계속 사용할 수 있지만 깨지면 사용할 수 없다. 만약에 수구가 하나만 남았다면 가장 작은 층부터 한 층 한 층 위로 올라가야 한다.
dp[i][j]는 i개의 수구가 j번 잃어버리면 측정할 수 있는 최대 높이를 나타낸다.
dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + 1.깨진 것과 깨지지 않은 가능성으로 나뉜다.
dp수 그룹을 처리하고 매번 가장 작은 j를 찾으면 dp[k][j]≥n을 찾으면 됩니다.
#include <stdio.h>
#include <string.h>
const int N = 105;
typedef long long ll;
int k;
ll n, dp[N][N];
void init () {
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 63; j++)
dp[i][j] = dp[i][j-1] + dp[i-1][j-1]+1;
}
}
bool judge () {
for (int i = 1; i <= 63; i++) {
if (dp[k][i] >= n) {
printf("%d
", i);
return true;
}
}
return false;
}
int main () {
init ();
while (scanf("%d%lld", &k, &n) == 2 && k && n) {
if (!judge()) printf("More than 63 trials needed.
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
