【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;
}