[HDU 6157] The Karting

一、题目

题目描述

\(n\) 个点排成一列,相邻两个点之间连边,\(i\)\(i+1\) 的双向边代价是 \(a_i\),转向的代价是 \(a_0\),现在我们想选出 \(m\) 个点,可以构成若干个回路,每个点最多被选一次,起点也算一次转向,试最大化代价。

比如选出的点是 1,3,2,4,那么回路是 1,2,3,2,3,4,3,2,1

数据范围

\(2\leq m\leq n\leq 100,-100\leq a_i\leq 100\)

二、解法

考虑回路上经过的每个点是困难的,所以我们只考虑端点,然后用前缀和计算回路的贡献。

\(dp\) 来处理端点,设 \(dp[i][j][k]\) 表示前 \(i\) 个点中,选出了 \(j\) 个端点,其中从左往右的端点比从右往左的端点多了 \(k\) 个(\(k\geq 0\)),转移考虑当前点的状态,一共四种情况:

  • 不选这个点:\(dp[i][j][k]\leftarrow dp[i-1][j][k]\)
  • 选了这个点但是不作为端点,随便从此经过:\(dp[i][j][k]\leftarrow dp[i-1][j-1][k]\)
  • 选了这个点作为从左往右的端点:\(dp[i][j][k]\leftarrow dp[i-1][j-1][k-1]+a_0-2\cdot s[i]\)
  • 选了这个点作为从右往左的端点:\(dp[i][j][k]\leftarrow dp[i-1][j-1][k+1]+a_0+2\cdot s[i]\)

因为要走回去,所以答案是 \(dp[n][m][0]\),时间复杂度 \(O(n^3)\)

三、总结

选端点作为 \(dp\) 的主体,转移中用到了费用提前计算的思想。

此外对于匹配问题(比如这道题是端点的配对),首先拆解贡献到匹配点上,考虑到某一个匹配点时候带着贡献和需要匹配的记号转移,这样就能够保证转移的顺序性。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 105;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<‘0‘ || c>‘9‘) {if(c==‘-‘) f=-1;}
	while(c>=‘0‘ && c<=‘9‘) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,a[M],dp[M][M][M];
void cmax(int &x,int y)
{
	x=max(x,y);
}
void work()
{
	for(int i=1;i<=n;i++)
		a[i]=a[i-1]+read();
	memset(dp,-0x3f,sizeof dp);
	dp[0][0][0]=0;
	for(int i=1;i<=n;i++)
	{
		dp[i][0][0]=0;
		for(int j=1;j<=m;j++)
			for(int k=0;k<=j;k++)
			{
				cmax(dp[i][j][k],dp[i-1][j][k]);
				cmax(dp[i][j][k],dp[i-1][j-1][k]);
				if(k) cmax(dp[i][j][k],dp[i-1][j-1][k-1]+a[1]-2*a[i]);
				cmax(dp[i][j][k],dp[i-1][j-1][k+1]+a[1]+2*a[i]);
			}
	}
	printf("%d\n",dp[n][m][0]);
}
signed main()
{
	while(~scanf("%d %d",&n,&m))
		work();
}

[HDU 6157] The Karting

上一篇:(续)MindSpore计算框架如何发布训练好的模型到官方模型仓库MindSpore_Hub上 —— 对fork的MindSpore_Hub进行PR提交


下一篇:EF Code First 强类型分页显示和删除