首页 > 代码库 > Codeforces 189A. Cut Ribbon
Codeforces 189A. Cut Ribbon
题目链接:http://codeforces.com/problemset/problem/189/A
题意：
给你一个长度为 N 的布条, 再给你三个长度 a, b , c.你可以用剪刀去剪这些布条, 但是每次剪完后, 布条的长度必须是 a 或者 b 或者 c, 问按照这个规则, 最多可以把这个布条剪成几段.
思路:
上述问题可以换一种说法, 这里有无线个长度为 a, b, c的布条, 让你选择最多的个数, 使得其连接起来长度恰好为 N.这很显然是根基础的完全背包的拓展问题.所以只解套用模板就好.
dp[i] = max( dp[i], dp[ i - v[j] ] + w[j] ).
代码:
1 #include <iostream> 2 #include <algorithm> 3 4 using namespace std; 5 typedef long long LL; 6 const int MAXN = 4000; 7 int dp[MAXN + 3] = {0}; 8 9 int main() {10 ios_base::sync_with_stdio(0); cin.tie(0);11 int n, abc[4]; cin >> n >> abc[0] >> abc[1] >> abc[2];12 for(int i = 1; i <= n; i++) dp[i] = -100000000; //dp[0] 初始化为 0, 其他初始化为负无穷13 for(int i = 0; i < 3; i++) for(int j = abc[i]; j <= n; j++) dp[j] = max(dp[j], dp[j - abc[i]] + 1);14 cout << dp[n] << endl;15 return 0;16 }
Codeforces 189A. Cut Ribbon
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。