caioj 1066 动态规划入门（一维一边推4：护卫队）（分组型dp总结）

很容易想到f[i]为前i项的最优价值，但是我一直在纠结如果重量满了该怎么办。

正解有点枚举的味道。

就是枚举当前这辆车与这辆车以前的组合一组，在能组的里面取最优的。

然后要记得初始化，因为有min，所以除0外初始化为最大，f[0] = 0

这实际上可以抽象出一种模型，就是一个区间线性分组的模型，都可以用这道题的方法写。

#include<cstdio>

#include<algorithm>

#include<cmath>

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

using namespace std;

typedef long long ll;

const int MAXN = 1123;

double v[MAXN], f[MAXN];

int w, len, n;

ll a[MAXN];

int main()

{

	scanf("%d%d%d", &w, &len, &n);

	REP(i, 1, n + 1)

	{

		int x, y;

		scanf("%d%d", &x, &y);

		a[i] = a[i - 1] + x;

		v[i] = len / (double)y * 60.0;

	}

	f[0] = 0.0;

	REP(i, 1, n + 1)

	{

		f[i] = 999999999999999.0; //一定要开很大，否则WA

		double t = 0;

		for(int j = i; j >= 1; j--)

		{

			if(a[i] - a[j - 1] > w) break;

			t = fmax(t, v[j]);

			f[i] = fmin(f[i], f[j - 1] + t);

		}

	}

	printf("%.1lf\n", f[n]);

	return 0;

}

巴特西

caioj 1066 动态规划入门（一维一边推4：护卫队）（分组型dp总结）

最新文章

热门文章