一、题目
题目描述
有 \(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();
}