本文主要是介绍【HDU】4960 Another OCD Patient 【DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】4960 Another OCD Patient
题目分析：比赛的时候写的太乱了，本来不需要合并的地方也合并了，现在重新改了改倒是清爽多了，顺便贴一下。
由于题目需要我们将原数组变成回文串，所以我们可以一开始就将原数组中必须合并的先合并了。那么什么是必须合并的呢？注意到左右对称，所以我们可以将左端的数相加正好等于右端的左右两个块分别合并（一定这样得到的是极小块），怎么相加呢？很简单，左边的数和比右边的小，左边再加一个数，右边的数和比左边的小，右边再加一个数，直到左右两边数相等时（合并）或者i>=j（退出）。
将得到的左右第 i 块中元素的数量用L[ i ]、R[ i ]表示，设得到左右得到的块数均为m（事实上左右的确是相等的）。
并设cost[ i ]为合并了i个元素的花费。
现在我们设dp[ i ]为添加了第L[ i ] 和R[ i ]块后形成回文串的最小花费。
dp[ i ] = min{ dp[ j - 1 ] + cost[ lnum[ j , i ] ] + cost[ rnum[ j , i ] ] | 1 <= j <= i , lnum[ j , i ]表示左边第j块到第i块元素个数总数，rnum[ j , i ]同理}。
最后再枚举中间合并的那一堆的数量，得到表达式minv = min{cost[ n ] , dp[ i ] + cost[ n - lnum[ i ] - rnum[ i ] ] | i <= m，lnum[ i ]表示从第1块到第i块的总元素个数，rnum[ i ]同理}。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
using namespace std ;#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )typedef long long LL ;const int MAXN = 5005 ;
const int INF = 0x3f3f3f3f ;int a[MAXN] , cost[MAXN] ;
int L[MAXN] , R[MAXN] , top ;
int dp[MAXN] ;
int n , m ;void solve () {top = 0 ;FOR ( i , 1 , n ) scanf ( "%d" , &a[i] ) ;FOR ( i , 1 , n ) scanf ( "%d" , &cost[i] ) ;for ( int i = 1 , j = n ; i < j ; ++ i , -- j ) {LL Lsum = a[i] , Rsum = a[j] ;int Lnum = 1 , Rnum = 1 ;while ( Lsum != Rsum ) {if ( i >= j ) break ;if ( Lsum < Rsum ) {++ Lnum ;Lsum += a[++ i] ;} else {++ Rnum ;Rsum += a[-- j] ;}}if ( Lsum == Rsum ) {++ top ;L[top] = Lnum ;R[top] = Rnum ;}}FOR ( i , 1 , top ) {int tmp1 = 0 , tmp2 = 0 ;dp[i] = INF ;REV ( j , i , 1 ) {tmp1 += L[j] ;tmp2 += R[j] ;dp[i] = min ( dp[i] , dp[j - 1] + cost[tmp1] + cost[tmp2] ) ;}}int minv = cost[n] , ans = n ;FOR ( i , 1 , top ) {ans -= L[i] + R[i] ;minv = min ( minv , dp[i] + cost[ans] ) ;}printf ( "%d\n" , minv ) ;
}int main () {while ( ~scanf ( "%d" , &n ) && n ) solve () ;return 0 ;
}这篇关于【HDU】4960 Another OCD Patient 【DP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
