C3-B

C3-B 钢管切割

题目描述

给定一段长度为$n$英寸的钢管和一个价格表，该价格表表示长度为$ i（i=1,2,\ldots,n）$英寸的钢管的价格为$p_i$。求钢管切割方案，使得总销售价格最大，注意钢管的长度必须为整英寸。

输入

第一行一个正整数 $n（1 \le n \le 10^4）$，表示钢管的总长度。

第二行$n$个正整数 $p_1,p_2,…,p_n(1≤pi≤10^7)$，表示钢管的价格。

输出

第一行一个正整数，表示最大总销售价格。

第二行一个正整数 $k$，表示钢管被分割成 k 段。

第三行$k$ 个正整数 $a1,…,ak$，表示钢管的分割方式，需保证$ ∑a_i=n$

如果有多种分割方案，输出任意一种即可。

题目分析

求切割方案，即求销售价格最大的子状态。设$dp[i]$为钢管长$i$时最大价格。可得状态转移方程如下：

$dp[i]=max(p[i],dp[1]+p[i-1],dp[2]+p[i-2],...,dp[i-1]+p[1])$

由于需要输出最后的切割方案，所以再开一个数组$ans[i]$在每次更新$dp[i]$时记录此时的$i-j$(新加入的一段钢管的长度)。最后输出$dp[n]$和$ans[i]$

$ans[i]$表示在钢管长为$i$时最后一段钢管的长度所以输出方式为：

for (int i = n; i > 0; i -= ansK[i])
{
    printf("%d ", ansK[i]);
}

示例代码

#include <stdio.h>
int p[10100];
long long int dp[10100];
int ansK[10100];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &p[i]);
    }
    dp[0] = 0;
    dp[1] = p[1];
    ansK[1] = 1;
    long long int max;
    for (int i = 2; i <= n; i++)
    {
        max = -1;
        for (int j = 0; j <= i; j++)
        {
            if (max < 1LL * p[i-j] + dp[j])
            {
                max = 1LL * p[i-j] + dp[j];
                ansK[i] = i-j;
            }
        }
        dp[i] = max;
    }
    printf("%lld\n", dp[n]);
    int num = 0;
    for(int i = n; i > 0; i-=ansK[i])
    {
        num++;
    }
    printf("%d\n", num);
    for (int i = n; i > 0; i -= ansK[i])
    {
        printf("%d ", ansK[i]);
    }
    return 0;
}