首页 > 其他分享 >HDU 6157 The Karting

HDU 6157 The Karting

时间:2023-01-21 15:11:39浏览次数:59  
标签:HDU int Karting 6157 转折点 MAXN max include

题目传送门

The Karting

思路分析

序列上的路径问题,可以转化成起点和终点的匹配问题,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

相关文章