网站建设做什么科目,zencart 官方网站,dw制作网页的过程,软考网络规划设计师正题 大意
有n株草#xff0c;没个时间单位开始时会增长不同的长度。每个时间单位可以将一株草剪成高度为0#xff0c;求多少时间单位后能够将草的总高度减低为h以下#xff0c;或用远不能。 解题思路
首先需要一段玄学推理#xff1a; 可以等草长高些在剪。 如果有解每…正题 大意
有n株草没个时间单位开始时会增长不同的长度。每个时间单位可以将一株草剪成高度为0求多少时间单位后能够将草的总高度减低为h以下或用远不能。 解题思路
首先需要一段玄学推理 可以等草长高些在剪。 如果有解每个草最多只需要剪一次因为如果要剪两次那么你可以在第一次的时候不用剪。 然后假设每一个草都要剪一次那么肯定先剪长得慢的因为等你剪后面的时候这个草又会飞快的长起来。
然后就可以用dp了先按照长得速度排序。然后用f[i][j]f[i][j]f[i][j]表示前i株长到第j秒时的最小长度。然后假设在k秒的时候能结束那么f[i−1][j]h[i]grow[i]∗kf[i−1][j]h[i]grow[i]∗kf[i-1][j]+h[i]+grow[i]*k表示不剪这株f[i−1][j−1]grow[i]∗(k−j)f[i−1][j−1]grow[i]∗(k−j)f[i-1][j-1]+grow[i]*(k-j)表示剪掉这株草。但是我们现在不知道k所以我们要枚举一下。动态转移方程
f[i][j]min(f[i−1][j]h[i]grow[i]∗k,f[i−1][j−1]grow[i]∗(k−j))f[i][j]min(f[i−1][j]h[i]grow[i]∗k,f[i−1][j−1]grow[i]∗(k−j))
f[i][j]=min(f[i-1][j]+h[i]+grow[i]*k,f[i-1][j-1]+grow[i]*(k-j))代码
#includecstdio
#includeiostream
#includealgorithm
using namespace std;
int n,hight,h[51],grow[51],f[51][51];
int main()
{scanf(%d%d,n,hight);for (int i1;in;i) scanf(%d,h[i]);for (int i1;in;i) scanf(%d,grow[i]);for (int i1;in;i)for (int ji1;jn;j)if (grow[j]grow[i]) {swap(grow[i],grow[j]);swap(h[i],h[j]);}for (int k0;kn;k){memset(f,127/3,sizeof(f));f[0][0]0;for (int i1;in;i)f[i][0]f[i-1][0]h[i]grow[i]*k;for (int i1;in;i)for (int j1;jk;j)f[i][j]min(f[i-1][j]h[i]grow[i]*k,f[i-1][j-1]grow[i]*(k-j));if (f[n][k]hight){printf(%d,k);return 0;}}printf(-1);
}
