uva 10688 - The Poor Giant(记忆化搜索）

题目链接：uva 10688 - The Poor Giant

题目大意：给出n和k，表示n个苹果，排成一列，重量分别是i+k，i为对应的第几个苹果,现在在这n个苹果中，有1个苹果是甜的，假设该苹果的序号为x，那么序号小于x的即为苦的，大于x的为酸的。求一个吃苹果的序列，要求可以找出甜得苹果，并且要求所有可能下的吃苹果质量和最小。

解题思路：记忆化搜索，dp[i][j]表示说甜得苹果在i~j之间时，需要的最小质量。但是因为在搜索的过程中，值还和先前吃得苹果质量有关，但是说因为要考虑所有情况下的质量和，所以可以将其单独出来计算，m*len。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 505;
const int INF = 0x3f3f3f3f;

int n, k, dp[N][N];

int solve (int l, int r, int m) {
	int s = (r-l+1)*m;
	if (dp[l][r] != INF)
		return s + dp[l][r];

	if (r == l) return s;

	int& ans = dp[l][r];
	for (int i = l; i <= r; i++) {
		int u = i+k;
		if (i != l) u += solve(l, i-1, i+k);
		if (i != r) u += solve (i+1, r, i+k);
		ans = min(ans, u);
	}
	return ans + s;
}

int main () {
	int cas;
	scanf("%d", &cas);
	for (int i = 1; i <= cas; i++) {
		memset(dp, INF, sizeof(dp));
		scanf("%d%d", &n, &k);
		printf("Case %d: %d\n", i, solve(1, n, 0));
	}
	return 0;
}