【UVa】【DP】10934 Dropping water balloons
UVa 10934 Dropping water balloons
제목.
◇ 제목 전송문◆(UVa가 느려 vjudge 링크 제공)◇ 제목 전송문(vjudge)◆
제목의 대의.
똑같은 수구가 KK개가 있고, N층 높이의 고층 건물에서 테스트가 진행된다.그러나 당신은 매우 게으르기 때문에 가장 적은 실험 횟수를 사용하여 수구의 경도가 도대체 얼마나 되는지 알고 싶다(어떤 층에서 던져서 마침 깨지면 수구의 경도는 이 층의 표호이다) 또는 가장 높은 층에서도 깨지지 않는다는 결론을 얻고 싶다.수구가 실험에 손상되지 않도록 주의해라. (즉, 이 공이 깨지지 않았다면, 이 공은 원래의 경도였다.)
최소한 필요한 실험 횟수를 구하다.63차례의 실험이 여전히 결과를 얻지 못하면 출력:
More than 63 trials needed.
.사고의 방향
2분?폭력KK의 제약이 생긴 것 같아서 모든 게 달라졌어...
우리는 사고방식을 바꾸었다. 수구의 개수와 실험 횟수를 정하고 가장 높은 실험 층을 구했다.이 문제는 DP로 바뀌었다.
정의 상태 f[i][j]f[i][j]는 ii개의 공을 사용하기 위해 jj차 실험을 할 수 있는 건물의 최고 층수를 측정한다.다음 단계에서는 의사 결정을 고려합니다.
현재 테스트 층을 kk로 설정합니다.
만약 수구가 k층에서 깨진다면 이전의 k-31k-3층은 반드시 i-3-1i-3개의 구 실험을 통해 j-1j-3을 1회 측정해야 한다는 것을 설명한다.그러면 k=f[i-3-1][j-3-1]+1k=f[i-31][j-3-1]+1일 때 이 결정이 가장 좋다.
만약 수구가 깨지지 않았다면 우리는 k+1k+1층을 11층으로 간주한 후에 f[i][j-31]f[i][j-31]층 건물을 계속 실험할 수 있다.
위에서 설명한 대로 상태 전환 방정식을 나열할 수 있습니다.
f[i][j]=f[i−1][j−1]+1+f[i][j−1] f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + 1 + f [ i ] [ j − 1 ]
세부 사항 구현
f[i][j]f[i][j]의 값이
int
을 초과할 수 있으니 long long
를 사용하십시오.규정된 시간 내에 출해를 보장하기 위해 타표법으로 모든 f[i][j]f[i][j]를 미리 처리하십시오.시간의 복잡도는 O(216)O(216)로 넘을 수 있다.
정해 코드
#include
#include
#include
using namespace std;
int K;
long long N;
long long f[65][65];
void Init() {
memset(f,0,sizeof f);
for(int i=1;i<64;i++)
for(int j=1;j<64;j++)
f[i][j]=f[i-1][j-1]+1+f[i][j-1];
}
int main() {
#ifdef LOACL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
Init();// , f[i][j]
while(scanf("%d %lld",&K,&N)!=EOF&&K&&N) {
K=min(K,63);//K 63 min!!!
// N<2^64, , 63
bool ok=false;
for(int i=0;i<64;i++)
if(f[K][i]>=N) {
printf("%d
",i);
ok=true;
break;
}// f[K][i] N
if(!ok)puts("More than 63 trials needed.");
// , 63
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.