UVA-10934 Dropping water balloons(思考+dp)
12047 ワード
トランスファゲート
非常に不思議な問題は、最小の実験回数を求めるように見えますが、実際にはプログラム本体はm i n minを使わず、問題を解決するために、LRJの考え方を見てみましょう.d[i][j]d[i][j]d[i][j]d[i][j]をiつの風船でj回試験できるビルの最高層数を実験し、最初の決定は、テストフロアをk kとします.風船が破れた場合は、前k−1 k−1 k−1層をi−1 i−1 i−1個の球でj−1 j−1 j−1を1回測定しなければならない、すなわちk=d[i−1][j−1]+1 k=d[i−1]+1 k=d[i−1][j−1]+1 k=d[i−1][j−1]+1 k=d[i−1][j−1]+1が最適 風船が破れていなければ、k+1階を1階以降の続きと見なすことになる.従って、k層の上にd[i][j−1]d[i][j−1]d[i][j−1]d[i][j−1]d[i][j−1]d[i][j]=k+d[i][j−1]=d[i−1][j−1]+d[i][j−1]d[i][j−1]d[i][j]=k+d[i][j−1]=d[i][j−1]=d[i][j−1]=d[i][j−1]=d[i−1][j−1]+d[j][j−1][j−1]+d[j][j−1][j−1]=d[j][j−1]+d[j][j−1]=d[j−918・
でもどうしてそう思うの?我々が実際に求めているのは,最小の試験回数に対応する最大の範囲である.もしそれが破れて、硬度がk k kより小さいことを示すならば、あなたはまだi−1 i−1 i−1気球とj−1 j−1 j−1実験を残して、1−(k−1)1−(k−1)1−(k−1)1−(k−1)1−(k−1)1−(k−1)の硬度範囲を確定することができなければならなくて、すなわちd(i−1,j−1)≧k−1 d(i−1,j−1)geq k−1 d(i−1,j−1)≧k−1、言い換えれば、私たちが選んだk k k k k k k k k k kはあまり大きくなくて、k<=d(i−1,j−1)+1 k<=d(i−1,j−1)+1 k<=d(i−1,j−1)+1が必要である.k番目のk層が破れていなければ、硬度がk番目のk層以上であり、i i i個の気球とj−1 j−1 j−1回の実験が残っていることを示し、決定可能な範囲をできるだけ拡大するためには、k+1 k+1 k+1層目を1層目とし、d(i,j−1)d(i,j−1)d(i,j−1)d(i,j−1)d(i,j−1)1)の方法を用いて以上の層を測定することが最適であり、このようにして決定できる最大範囲は[1,a]+d(i,j−1)[1,a]+d(i,j−1)[1,a]+d(i,j−1),すなわちd(i,j)=ma x(k+d(i,j−1)=d(i−1,j−1)+d(i,j−1)+d(i,j−1)+d(i,j−1)+d(i,j−1)+1 d(i,j−1)+d(i,j−1)=max(k+d(k+d(k+d(k+d,j−1)=d(i−1,j−1)+d(i,j−1)+d(i,j)=max(k+d(k+d+(i,j−1)=d(i−1,j−1)+d(i,j−1)+1
reference:簡書kinoud
ここまで言うと、まだ少し分からないことがあります.ゆっくり理解してください.次のもっと良い文章があります.
Click Here
非常に不思議な問題は、最小の実験回数を求めるように見えますが、実際にはプログラム本体はm i n minを使わず、問題を解決するために、LRJの考え方を見てみましょう.d[i][j]d[i][j]d[i][j]d[i][j]をiつの風船でj回試験できるビルの最高層数を実験し、最初の決定は、テストフロアをk kとします.
でもどうしてそう思うの?我々が実際に求めているのは,最小の試験回数に対応する最大の範囲である.もしそれが破れて、硬度がk k kより小さいことを示すならば、あなたはまだi−1 i−1 i−1気球とj−1 j−1 j−1実験を残して、1−(k−1)1−(k−1)1−(k−1)1−(k−1)1−(k−1)1−(k−1)の硬度範囲を確定することができなければならなくて、すなわちd(i−1,j−1)≧k−1 d(i−1,j−1)geq k−1 d(i−1,j−1)≧k−1、言い換えれば、私たちが選んだk k k k k k k k k k kはあまり大きくなくて、k<=d(i−1,j−1)+1 k<=d(i−1,j−1)+1 k<=d(i−1,j−1)+1が必要である.k番目のk層が破れていなければ、硬度がk番目のk層以上であり、i i i個の気球とj−1 j−1 j−1回の実験が残っていることを示し、決定可能な範囲をできるだけ拡大するためには、k+1 k+1 k+1層目を1層目とし、d(i,j−1)d(i,j−1)d(i,j−1)d(i,j−1)d(i,j−1)1)の方法を用いて以上の層を測定することが最適であり、このようにして決定できる最大範囲は[1,a]+d(i,j−1)[1,a]+d(i,j−1)[1,a]+d(i,j−1),すなわちd(i,j)=ma x(k+d(i,j−1)=d(i−1,j−1)+d(i,j−1)+d(i,j−1)+d(i,j−1)+d(i,j−1)+1 d(i,j−1)+d(i,j−1)=max(k+d(k+d(k+d(k+d,j−1)=d(i−1,j−1)+d(i,j−1)+d(i,j)=max(k+d(k+d+(i,j−1)=d(i−1,j−1)+d(i,j−1)+1
reference:簡書kinoud
ここまで言うと、まだ少し分からないことがあります.ゆっくり理解してください.次のもっと良い文章があります.
Click Here
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=105;
ll d[maxn][maxn];
ll n,k;
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(int i=1;i<=maxn;i++)
for(int j=1;j<=63;j++)
d[i][j]=d[i-1][j-1]+d[i][j-1]+1;
while(~scanf("%lld%lld",&k,&n) && k){
int ans=-1;
for(int i=1;i<=63;i++)
if(d[k][i]>=n){
ans=i;
break;
}
if(ans<0) printf("More than 63 trials needed.
");
else printf("%d
",ans);
}
return 0;
}