企业官网建设流程全解析

题意分析

我们定义dp[x]：拼成总长度为x的棒，能得到的最大武力值。

规则：

1. 基础情况：直接用一根短棒a_i，如果a_i = x，那么dp[x]可以取b_i。
2. 合并规则：把两根棒（长度 A、B）拼接成长度A+B的棒：
   • 若A != B：dp[A+B] = max(dp[A+B], dp[A] + dp[B])
   • 若A == B = K：dp[2K] = max(dp[2K], dp[K] * 2 + 233)

短棒无限数量，目标求dp[M]。

算法思路

1. 初始化 dp 数组：dp大小为M+1，初始值设为负无穷。
2. 预处理：对于每一种短棒(a_i,b_i)，如果a_i <= M，更新dp[a_i] = max(dp[a_i], b_i)。
3. 从小到大枚举长度len（从 1~M）：
   • 枚举 A 从1 ~ len/2，B = len - A
   • 如果dp[A]和dp[B]不是负无穷（代表 A、B 都可以拼出来）
     • 如果A == B：dp[len] = max(dp[len], dp[A]*2 +233)
     • 如果A != B：dp[len] = max(dp[len], dp[A]+dp[B])
4. 最后输出dp[M]

为什么从小到大遍历？因为要拼出长度 len，需要的 A,B 一定比 len 小，已经提前算好 dp [A], dp [B]。

c++代码

#include<bits/stdc++.h> using namespace std; const int N=1e3+10,M=1e3,V=233,INF=1e8; int n,m,a[N],b[N],dp[N]; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=M;++i)dp[i]=-INF; for(int i=1;i<=n;++i){ scanf("%d",&a[i]); } for(int i=1;i<=n;++i){ scanf("%d",&b[i]); for(int j=a[i];j<=M;++j){ dp[j]=max(dp[j],dp[j-a[i]]+b[i]); } } for(int i=2;i<=M;++i){ dp[i]=max(dp[i],dp[i/2]*2+V); for(int j=1;j<i;++j){ dp[i]=max(dp[i],dp[j]+dp[i-j]); } } printf("%d\n",dp[m]); return 0; }