网站开发常见面试题,seo网站设计外包,江西企业网站建设公司,织梦 xml 网站地图D. Towers
设计dp#xff1a; fif_ifi表示考虑到iii时满足题意的最小代价。 考虑最后一步#xff0c;也就是最后一组合并即fifj{aj1⋯ai}f_if_j\{a_{j1}\dotsa_i\}fifj{aj1⋯ai} 在满足最优条件的同时让当前aia_iai最小#xff08;贪心#xff09;
#include fif_ifi表示考虑到iii时满足题意的最小代价。 考虑最后一步也就是最后一组合并即fifj{aj1⋯ai}f_if_j\{a_{j1}\dotsa_i\}fifj{aj1⋯ai} 在满足最优条件的同时让当前aia_iai最小贪心
#includebits/stdc.husing namespace std;constexpr int N5010;
int a[N],s[N],f[N];
int n;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;for(int i1;in;i) cina[i];for(int i1;in;i) s[i]s[i-1]a[i];memset(f,0x3f,sizeof f);f[0]0;memset(a,0x3f,sizeof a);a[0]0;for(int i1;in;i)for(int j0;ji;j)// j1~i合并if(a[j]s[i]-s[j]f[j]i-j-1f[i])// 保证满足 aj (aj1...ai){f[i]f[j]i-j-1;if(a[i]s[i]-s[j]) a[i]s[i]-s[j];// 贪心}coutf[n]\n;return 0;
}
