【題解】ZeroJudge a261: 10934 – Dropping water balloons

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a261
【解題想法】DP

  • a[i][j]:i 是丟水球的次數,j 是目前還沒破的水球的顆數。a[i][j] 表示 (i, j) 條件下可檢查的最高樓層數。
  • 狀態轉移:a[i][j] = a[i-1][j-1] + 1 + a[i-1][j];
#include <iostream>
using namespace std;

int k;
long long n, a[64][105];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 1; i <= 63; i++){
        for (int j = 1; j <= 100; j++){
            a[i][j] = a[i-1][j-1] + 1 + a[i-1][j];
        }
    }
    while (cin >> k >> n){
        if (k == 0) break;
        if (n > a[63][k]){
            cout << "More than 63 trials needed.\n";
            continue;
        }
        for (int i = 1; i <= 63; i++){
            if (n <= a[i][k]){
                cout << i << "\n";
                break;
            }
        }
    }
}
分享本文 Share with friends