思路
- 基础 d p dp dp ， d p i , j dp_{i,j} dpi,j 表示长度为 i i i ， p i e c e piece piece 为 j j j 的数量。题目范围 4000 4000 4000 常规定义可能会 M E L MEL MEL ，所以第二维为不同的 p i e c e piece piece 的个数。
- 枚举不同的 p i e c e s pieces pieces 长度。
- 方程： d p i , j = d p i − l e n j , j + 1 / 0 dp_{i,j}=dp_{i-len_j,j}+1/0 dpi,j=dpi−lenj,j+1/0 。（是当前枚举长度则为 1 1 1 )
Think Twice, Code Once文章来源地址https://www.toymoban.com/news/detail-799891.html
signed main() {
int T = 1;
// T = read();
while (T--) {
int n = read();
vector<int> vec;
for (int i = 1; i < 4; ++i) {
int u = read();
vec.push_back(u);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
vector<vector<int>> dp(4000 + 10, vector<int>(vec.size()));
auto get_sum = [&] (int j) {
int res = 0;
for (int i = 0; i < vec.size(); ++i) res += dp[j][i];
return res;
};
for (int i = 0; i < vec.size(); ++i) dp[vec[i]][i] = 1;
for (int i = 1; i <= n; ++i) {
int sum = 0;
for (int j = 0; j < vec.size(); ++j) {
if (i - vec[j] >= 0) {
int tmp = get_sum(i - vec[j]);
if (sum < tmp) {
sum = tmp;
for (int k = 0; k < vec.size(); ++k) dp[i][k] = dp[i - vec[j]][k] + (k == j);
}
}
}
}
write(get_sum(n));
}
return 0;
}
//3119 3515 1021 7
文章来源：https://www.toymoban.com/news/detail-799891.html
到了这里，关于codeforces A -Cut Ribbon的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
