UVa-882, POJ-2904 : The Mailbox Manufacturers Problem

問題概要

K個のポストがある。ポストを壊すのに爆弾が最低いくつ必要かをしりたい。最低爆弾をいくつ用意する必要があるか求める問題。

解法

状態を(残りポスト、下限、上限)としてDP。

acceptされたコード

計算量O(K*M^3)。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_K = 10;
const int MAX_M = 100;
const int INF = 1<<29;

int K, M;
bool visited[MAX_K + 1][MAX_M + 2][MAX_M + 2];
int memo[MAX_K + 1][MAX_M + 2][MAX_M + 2];

int rec(const int k, const int low, const int high){
	if(visited[k][low][high]){
		return memo[k][low][high];
	}
	visited[k][low][high] = true;

	int& ret = memo[k][low][high];
	ret = INF;

	if(low > high){
		return ret = 0;
	}
	if(low == high){
		return ret = 0;
	}
	if(k == 0 && low != high){
		return ret = INF;
	}

	for(int i=low; i<=high; i++){
		ret = min(ret, i + max(rec(k, i+1, high), rec(k-1, low, i)));
	}

	return ret;
}

void init(){
	scanf("%d%d", &K, &M);
	memset(visited, false, sizeof(visited));
}

int solve(){
	return rec(K, 1, M + 1);
}

int main(){
	int T;
	scanf("%d", &T);
	for(;T--;){
		init();
		printf("%d\n", solve());
	}

	return 0;
}