P76040 剪成最多段 — 题解

专题： 动态规划
适用题目： 新生 OJ 本地题包中的 P76040，不要直接用于外站同名题。

解题思路

设 f[i] 表示恰好剪出总长度 i 时的最多段数，尝试从 i-a、i-b、i-c 转移。

复杂度

时间 $O(3n)$，空间 $O(n)$。

易错点

不可达状态应设置为很小的负数，不能误当作 0。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    int n,a,b,c;scanf("%d%d%d%d",&n,&a,&b,&c);
    int *f=malloc((n+1)*sizeof(int));
    for(int i=0;i<=n;i++)f[i]=-100000000;
    f[0]=0;int len[3]={a,b,c};
    for(int i=1;i<=n;i++)for(int j=0;j<3;j++)if(i>=len[j]){
        int v=f[i-len[j]]+1;
        if(v>f[i])f[i]=v;
    }
    printf("%d\n",f[n]);free(f);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    vector<int>f(n+1,-100000000);
    f[0]=0;
    for(int i=1;i<=n;i++)for(int len:{a,b,c})if(i>=len)f[i]=max(f[i],f[i-len]+1);
    cout<<f[n]<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。