题目传送门
思路分析
序列上的路径问题,可以转化成起点和终点的匹配问题,dp 匹配的权值,记录匹配的标记就可做
数据很小,支持\(O(n^3)\)
看起来可以直接dp
引入一种新的思路:只考虑端点,利用前缀和记录贡献
卡丁车运行过程中共有4种状态:不走此点、路过、左转、右转
注意k的意义是区分左转和右转端点
f[i][j][k] = max(f[i][j][k] , f[i-1][j][k]) ;//不选这个点
f[i][j][k] = max(f[i][j][k] , f[i-1][j-1][k]) ;//选这个点但是只是路过,不是转折点
if(k) f[i][j][k] = max(f[i][j][k] , f[i-1][j-1][k-1] + a[1] - 2 * a[i]) ;//是左转折点
f[i][j][k] = max(f[i][j][k] , f[i-1][j-1][k+1] + a[1] + 2 * a[i]) ;//是右转折点
·+或-\(2a[i]\)是利用前缀和计算的方法
·k的加减与正常相反是因为是从原来的状态转移而来
code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std ;
const int MAXN = 205 ;
int n ,m ;
int f[MAXN][MAXN][MAXN] ;
int a[MAXN] ;
int main(){
while(~scanf("%d%d" , &n , &m)){
for(int i = 1;i <= n;++i) scanf("%d" , a + i) ,a[i] += a[i - 1] ;
memset(f , -0x3f , sizeof f) ;
f[0][0][0] = 0 ;
for(int i = 1;i <= n;++i){//前i个端点
f[i][0][0] = 0 ;
for(int j = 1;j <= m;++j){//选中了j个端点
for(int k = 0;k <= j;++k){//左往右比右往左多了k个
f[i][j][k] = max(f[i][j][k] , f[i-1][j][k]) ;//不选这个点
f[i][j][k] = max(f[i][j][k] , f[i-1][j-1][k]) ;//选这个点但是只是路过,不是转折点
if(k) f[i][j][k] = max(f[i][j][k] , f[i-1][j-1][k-1] + a[1] - 2 * a[i]) ;//是左转折点
f[i][j][k] = max(f[i][j][k] , f[i-1][j-1][k+1] + a[1] + 2 * a[i]) ;//是右转折点
}
}
}
printf("%d\n" , f[n][m][0]) ;
}
return 0 ;
}
/*
4 2
1 1 1 -1
*/
标签:HDU,int,Karting,6157,转折点,MAXN,max,include
From: https://www.cnblogs.com/adolf-stalin/p/17063835.html