石子合并

最经典的区间dp题。

思路

让我们先看最简单的，两堆石子合并。费用自然只能是两组石子之和。

那么三堆呢？我们可以先合并前两个或后两个，无论怎么合并，最后一步费用一定是三组石子之和。

四堆中，我们从左往右有三种方法合并，但每一种最后一步费用一定是整段的和。

那么让我们推广到n堆石子合并，合并的方法有n-1种，而每一种方法都可以表示为将某堆以及该堆左边所有石子合并，再把右边所有石子一起合并,

所以我们不妨在区间中枚举一个断点，以此求区间最值。因为每一种方法都可能是最小的，我们为了求长度为n的区间，需要求出长度从2到n-1所有区间的长度。

于是聪明的你一定已经想到了状态转移方程：

让我们枚举一个断点i。

$\red{dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]+整段的和)}$

好了，结束。

代码

int Dp[500][500];
int a[500], Sum[500];
int n;

int main()
{
    scanf("%d", &n);
    memset(dp,0x3f,sizeof(dp)); //为了求最小值
    for (int i = 1;i <= n;i++)
    {
        dp[i][i]=0; //合并一堆石头不需费用
        scanf("%d", &Sum[i]), Sum[i] += Sum[i-1];// 每一步都需要区间求和，不妨用前缀和
    }
    for (int len = 2;len <= n;len++) //区间长度
        for (int l = 1,r=len;r <= n;l++,r++) // 左右端点
            for (int k = l;k < r;k++)//枚举断点
                Dp[l][r] = min(Dp[l][r], Dp[l][k]+Dp[k+1][r]+Sum[r]-Sum[l-1]);
    printf("%d\n", Dp[1][n]);
}

代码直上

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=305;
const int INF=0x3f3f3f3f;
int dp[N][N];
int a[N];
int sum[N];
int main(){
	cin>>n;
	memset(dp,INF,sizeof(dp));
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		dp[i][i]=0;
	}
	//区间dp模板
	for(int len=2;len<=n;len++){
    	for(int i=1;i<=n-len+1;i++){
       		int j=i+len-1;
       		for(int k=i;k<=j-1;k++){ 
         	    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
     		}
   		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}

剪贴板食用更加。

题意分析

求全题中的最优解，相当与把所有的石子堆按一个割点分割成两段。然后再分，再分，……，求最小的体力值。

所以这是一道很经典的区间dp。

前置知识

• 什么是区间dp

  很简单（请原谅我使用如此恶劣的词汇），就是求一个区间的最优解。

• 递增公式

  设有一个数串$\red{a}$, 且 $\red{a_i = a_{i-1}+1}$, $\red{a_1 = x}$ , 则：

  • 若已知右端点$\red{a_r}$, 则$\red{a_l\sim a_r}$的长度为$\red{a_r-a_l+1}$
  • 若已知左端点($\red{a_l}$)和长度，则$\red{a_r=a_l+长度-1}$
  • 若已知右端点($\red{a_r}$)和长度，则$\red{a_l=a_r-长度+1}$

• 无穷大的C++版：0x3f3f3f3f，原因可看一下这篇博文，里面还把memset版的无穷大给写了出来。

思路

1. 先枚举区间的长度

   为什么呢？如果你去枚举端点，你无法保证区间长度递增，因此无法求得最优解。

2. 再枚举起点，通过递增公式求出右端点，并保证右端点不越界。

3. 枚举割点，把割点左边给合起来，右边的合起来，再把全部合起来，进行比较，即可得到一种解。求最小值即可。(可用前缀和来求整段的和）注意初始化dp数组为无穷大。

   转移方程：$\red{dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]+整段的和)}$

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cctype>
#include <iomanip>
using namespace std;

int dp[305][305];
int a[305], sum[305];
int n;

int main()
{
    int N;
    cin >> N;
    memset(dp,0x3f,sizeof(dp));
    for (int i = 1;i <= N;i++)
    {
        dp[i][i] = 0;
        int x;
        cin >> x;
        sum[i] = sum[i - 1] + x;
    }
    for(int i = 2;i <= N;i++)
    {
        for(int l = 1,r = i;r <= N;l++,r++)
        {
            for(int k = l;k < r;k++)
            {
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + (sum[r] - sum[l-1]));
            }
        }
    }
    cout << dp[1][N];
}

/*****************************************
Note：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int a[N] , dp[300][300];
int main()
{
	int n ;
	cin >> n;
	for(int i = 1 ; i <= n ;i++)
	{
		cin >> a[i];
		a[i] += a[i-1];
	}
	for(int k = 2 ; k <= n ; k++)
	{
		for(int l = 1 ; l+k -1 <= n ; l++)
		{
			int r = l + k - 1;
			dp[l][r] = INF;
			for(int i = l ; i < r ; i++)
			{
				dp[l][r] = min(dp[l][r] , dp[l][i] + dp[i+1][r] + a[r] - a[l-1]);
			}
		}
	}
	cout << dp[1][n] << endl;
	return 0;
}