网站内容优化细节,邢台专业做网站公司,永州市城乡建设中等职业技术学校网站,wordpress 安装不了//当我们将棍子分段之后#xff0c;我们是不是想到了怎么组合这些棍子 //并且这些棍子有一个性质就是只能与相邻的进行组合 //暴力搜索的话复杂度很高 //在思考暴力搜索的时候#xff0c;我们发现一个规律 //比如棍子长度1 2 1 1 2 //那么与最后一个2组合的棍子有#xff0c… //当我们将棍子分段之后我们是不是想到了怎么组合这些棍子 //并且这些棍子有一个性质就是只能与相邻的进行组合 //暴力搜索的话复杂度很高 //在思考暴力搜索的时候我们发现一个规律 //比如棍子长度1 2 1 1 2 //那么与最后一个2组合的棍子有1 21 1 2,2 1 1 2,1 2 1 1 2 //与最后一个1组合的棍子有,1 1,2 1 1,1 2 1 1 //发现一个很显然的规律能与前面组合的只有前面已经组合过的才能组合在一起 //这是左边那么当然还有右边 //同理也是 //然后根据规律总结一下公式 //假设1 2 1 1 2下标对应0 1 2 3 4 //设f[i][j]表示组成这个区间的棍子的成本 //那么想组成f[0][4] f[0][3] a[4]; //f[1][4] f[1][3] a[4]; //f[2][4] f[2][3] a[4]; //f[3][4] f[3][3] a[4]; //从这里又能看出我们组合肯定是根据范围从小到大进行组合的 //比如f[1][3] f[1][2] f[2][3];那么在统计范围大的区间时 //是由前面一个小范围推过来的所以故此在计算大范围之前先统计小范围 //故这就是动态规划的阶段 //本题中我们求的是最小成本那么需要把所有能组成f[0][4]的最小成本在推导时取个min就可以了 class Solution {
public:int minCost(int n, vectorint cuts) {sort(cuts.begin(),cuts.end());vectorint a;int prev 0;for(int i 0;i cuts.size();i){a.push_back(cuts[i] - prev);prev cuts[i];}a.push_back(n - prev);//当我们将棍子分段之后我们是不是想到了怎么组合这些棍子//并且这些棍子有一个性质就是只能与相邻的进行组合//暴力搜索的话复杂度很高//在思考暴力搜索的时候我们发现一个规律//比如棍子长度1 2 1 1 2//那么与最后一个2组合的棍子有1 21 1 2,2 1 1 2,1 2 1 1 2//与最后一个1组合的棍子有,1 1,2 1 1,1 2 1 1//发现一个很显然的规律能与前面组合的只有前面已经组合过的才能组合在一起//这是左边那么当然还有右边//同理也是//然后根据规律总结一下公式//假设1 2 1 1 2下标对应0 1 2 3 4//设f[i][j]表示组成这个区间的棍子的成本//那么想组成f[0][4] f[0][3] a[4];//f[1][4] f[1][3] a[4];//f[2][4] f[2][3] a[4];//f[3][4] f[3][3] a[4];//从这里又能看出我们组合肯定是根据范围从小到大进行组合的//比如f[1][3] f[1][2] f[2][3];那么在统计范围大的区间时//是由前面一个小范围推过来的所以故此在计算大范围之前先统计小范围//故这就是动态规划的阶段//本题中我们求的是最小成本那么需要把所有能组成f[0][4]的最小成本在推导时取个min就可以了//1 2 1 1 2int f[110][110];memset(f,0x3f3f3f3f,sizeof(f));vectorint b(a.size() 1);for(int i 0;i a.size();i) b[i 1] a[i];for(int i 1;i a.size();i) f[i][i] 0;int s[110];memset(s,0,sizeof(s));for(int i 1;i a.size();i) s[i] s[i - 1] b[i]; for(int len 2;len a.size();len)//枚举的范围和阶段{for(int l 1;l len - 1 a.size();l)//确定范围把当前阶段的状态都枚举出来{int r l len - 1;for(int k l;k r;k)//确定好范围之后我们就可以更新当前范围的状态了//怎么样保证不漏掉呢只要枚举l k r之间的k就行可以保证所有状态都有{ f[l][r] min(f[l][r],f[l][k] f[k 1][r] s[r] - s[l - 1]);}}}return f[1][a.size()];}
};
