caioj 1081 动态规划入门（非常规DP5：观光游览）

这道题和前面的分组的题有点像

就是枚举最后一组的长度。

然后组数可以在第一层循环也可以在第二层循环

我自己的话就统一一下在第一层循环吧

然后这道题题意我一直没理解清楚，浪费了很多时间，写复杂了

同时初始化的问题很重要。

f[i][j]为前i格j个人分配的最大值

f[0][0] = 0,其他为负无穷

因为这道题很严格，有些状态是不存在的（比如前5格分配6个人），这个时候就要设负无穷表示不存在

这个要注意

然后一开始我走进了一个坑

一开始我加了

REP(i, 0, k + 1) f[0][i] = 0;

REP(i, 0, m + 1) f[i][0] = 0;

然后WA

这样算出来的答案的人数可以少于k个人

而题目说的是必须k个人

我这样设f[0][i] = 0,往后推的话会少掉一些人（自己体会）

所以初始化千万要注意，不要乱设为0

#include<cstdio>

#include<algorithm>

#include<cstring>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

int f[MAXN][MAXN], sum[MAXN][MAXN], n, m, k;

struct node

{

	int l, r, v;

}a[MAXN];

int main()

{

	scanf("%d%d", &m, &n);

	REP(i, 1, n + 1) scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].v);

	scanf("%d", &k);

	REP(i, 1, m + 1)

		REP(j, i, m + 1)

			REP(r, 1, n + 1)

				if(i <= a[r].l && a[r].r <= j)

					sum[i][j] += a[r].v;

	memset(f, -63, sizeof(f));

	f[0][0] = 0;

	REP(j, 1, k + 1)

		REP(i, 1, m + 1)

			REP(r, 1, i + 1)

				f[i][j] = max(f[i][j], f[r-1][j-1] + sum[r][i]);

	printf("%d\n", f[m][k]);

	return 0;

}

巴特西

caioj 1081 动态规划入门（非常规DP5：观光游览）

最新文章

热门文章