uva10934

1666 ワード

紫書第九章ダイナミックプランニング

題意:k個の風船、n階を与えて、出力は少なくとも何回の実験を必要としてやっと砕ける階を確定することができます.
1つ目は、d[i][j]がi個の気球でj回の試験可能なビルの最高層数を実験し、1回目の決定で、試験フロアをkとした.
気球が破れた場合,前k−1層はi−1球実験j−1回で測定できなければならない,すなわちk=d[i−1][j−1]+1が最適であることを示した.
風船が破れていなければ、k+1階を1階以降の続きと見なすことになる.したがって、k階の上にd[i][j-1]階、すなわちd[i][j]=k+d[i][j-1]=d[i-1][j-1]+d[i][j-1]をテストすることもできる.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 100;
int d[maxn+10][maxn+10];
int main() {
	int n, k;
	memset(d, 0, sizeof(d));
	for (int i = 1; i <= maxn; i++) {
		for (int j = 1; j <= 63; j++) {
			d[i][j] = d[i - 1][j - 1] + 1 + d[i][j - 1];
		}
	}
	while (cin >> k >> n && k) {
		int ans = -1;
		for (int i = 1; i <= 63; i++) {
			if (d[k][i] >= n) {
				ans = i; break;
			}
		}
		if (ans < 0)cout << "More than " << 63 << " trials needs\ed" << endl;
		else cout<

第2種
d[i][j]i個の携帯電話j階の最小テスト回数、d[i][j]=min(d[i][j],max(d[i-1][k-1],d[i][j-k]+1))d[i-1][j-1]はテスト階が破れたことを示し、このときi-1個があり、k-1個の階をテストする必要があり、破れず、j-k個の階をテストする必要がある.

void dp(int n,int k) {
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			d[i][j] = j;
		}
	}
	for (int i = 2; i <= k; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k < j; k++) {
				d[i][j] = min(d[i][j], max(d[i - 1][k - 1], d[i][j - k]) + 1);
			}
		}
	}
}

Queue

Python(4)