PKU 3783-Balls

英語難しすぎる…。

問題概要

N階以上の高さの階から落とすと壊れるボールがB個ある。
ビルの高さがP階であるとき、Nを確実に求めるのに必要なボールを落とす回数を求めよ。

解法

B個のボールをP階から落とす時の回数をDFSで求め、メモ化する。
DPでも解けるらしいが漸化式を立てるのが面倒だったのでやらなかった。

実装(C++)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


#define REP(i,x) for(int i=0;i<(int)(x);i++)

int main(){
	int P;
	for(scanf("%d",&P);P--;){
		int t,n;
		scanf("%d%d",&t,&n);
		vector<int> in(n);
		REP(i,n){
			scanf("%d",&in[i]);
		}
		int v=0;
		REP(i,n){
			bool ok=true;
			int cnt=0;
			v+=in[i];
			for(int j=i+1;j<n;j++){
				cnt+=in[j];
				if(cnt>v){
					ok=false;
					break;
				}else if(cnt==v){
					cnt=0;
				}
			}
			if(ok&&cnt==0){
				cout<<t<<" "<<v<<endl;
				break;
			}

		}
	}
	return 0;
}