USACO13NOV SILVER POGO的牛Pogo-Cow

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Thu Nov 08 09:01:58 CST 2018

In Category: NoCategory

Description：

有 $n$ 个点，每次可以往后跳，要求跳的距离越来越长，并且每次跳到某个点上，获得这个点的得分，求最大得分。

$1\leqslant n\leqslant 10^3$

Solution：

设 $f[i][j]$ 表示上一次在 $i$ ，这次在 $j$ 的最大得分，转移时可以用双指针，就是随着 $k$ 右移，合法的 $i$ 也在左移，这样只要维护一个当前最大值就可以转移了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1010

struct cow

{

	int x,v;

}s[MAXN];

bool cmp_x(cow a,cow b){return a.x < b.x;}

int f[MAXN][MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&s[i].x,&s[i].v);

	}

	sort(s + 1,s + 1 + n,cmp_x);

	memset(f,0xc0,sizeof(f));

	for(int i = 1;i <= n;++i)f[i][i] = s[i].v;

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		int maxv = 0xc0c0c0c0;

		for(int j = i + 1,k = i + 1;j <= n;++j)

		{

			while(k > 0 && s[i].x - s[k - 1].x <= s[j].x - s[i].x)

			{

				--k;

				maxv = max(maxv,f[k][i]);

			}

			f[i][j] = max(f[i][j],maxv + s[j].v);

			ans = max(ans,f[i][j]);

		}

	}

	for(int i = 1;i <= n;++i)

	{

		s[i].x = 1000000 - s[i].x;

	}

	sort(s + 1,s + 1 + n,cmp_x);

	memset(f,0xc0,sizeof(f));

	for(int i = 1;i <= n;++i)f[i][i] = s[i].v;

	for(int i = 1;i <= n;++i)

	{

		int maxv = 0xc0c0c0c0;

		for(int j = i + 1,k = i + 1;j <= n;++j)

		{

			while(k > 0 && s[i].x - s[k - 1].x <= s[j].x - s[i].x)

			{

				--k;

				maxv = max(maxv,f[k][i]);

			}

			f[i][j] = max(f[i][j],maxv + s[j].v);

			ans = max(ans,f[i][j]);

		}

	}

	cout << ans << endl;

	return 0;

}

In tag: DP-前缀和优化DP 技巧-双指针

wjh15101051