3 条题解

  • 1
    @ 2021-11-14 11:20:13

    剪贴板食用更加。

    题意分析

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

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

    前置知识

    • 什么是区间dp

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

    • 递增公式

      设有一个数串a\red{a}, 且 ai=ai1+1\red{a_i = a_{i-1}+1}, a1=x\red{a_1 = x} , 则:

      • 若已知右端点ar\red{a_r}, 则alar\red{a_l\sim a_r}的长度为aral+1\red{a_r-a_l+1}
      • 若已知左端点(al\red{a_l})和长度,则ar=al+长度1\red{a_r=a_l+长度-1}
      • 若已知右端点(ar\red{a_r})和长度,则al=ar长度+1\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];
    }
    

    信息

    ID
    193
    时间
    5000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    196
    已通过
    64
    上传者