一道ACM题--A. Cut Ribbon http://www.codeforces.com/problemset/problem/189/A

答案:2 悬赏:60 手机版

解决时间 2021-02-23 23:07

提问者网友：留有余香
2021-02-23 10:46

#include
#include
#include
#include
#include
#include
#include
#include
#include
usingnamespace std;
int dp[4100];int n, a, b, c;int inf=-1000000;int main (){
cin>>n>>a>>b>>c;
dp[0]=0;for(int i=1;i<=n;i++){
dp[i]=inf;if(i-a>=0)
dp[i]=max( dp[i], dp[i-a]+1);if(i-b>=0)
dp[i]=max( dp[i], dp[i-b]+1);if(i-c>=0)
dp[i]=max( dp[i], dp[i-c]+1);}
cout<>n;}某大神的答案，该如何理解？本人水货一枚，求大神给出详细解答（不详细的我怕我理解不了）谢谢0.0

最佳答案

五星知识达人网友：低血压的长颈鹿
2021-02-23 10:59

这题是用动态规划做的：
dp[i]表示长度为i的ribbon可以分成的最大份数。
<初始状态> dp[0]=0，dp[i]==-1000000表示长度i不可分为a,b,c。
<状态转移> 若i可分，则(i-a),(i-b),(i-c)中至少有一个可分。
dp[i] = max{dp[i-a]+1,dp[i-b]+1,dp[i-c]+1}

从1推到n，dp[n]就是答案了

全部回答

1楼网友：胯下狙击手
2021-02-23 11:48

你好！把题目说一下。——望采纳~ 记得给问豆啊！

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！