DP --NYOJ 整理图书

/*dphttp://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=1216题意：n堆书，相邻两堆可以合并，要求书堆按照非递减的顺序排列，问最少的合并次数思路：dp[i]表示合并前i堆的最少次数mx[k]记录前k堆书的最高高度sum[i]表示前i堆的总高度最外层循环控制dp[i]，然后根据i往前寻找第一个k,使得k+1堆到i堆书的总高度 大于等于 前k堆最高的高度，如果能满足这个条件，就符合题目中非递减的要求，因为前k堆我们已经计算出了符合要求的最少次数 */
# include 
# include 
# include 
# include 
# include using namespace std;int main(void)
{
//  freopen("in.txt","r",stdin);int n,cnt=1;while(cin >> n){int num[1005],sum[1005],mx[1005],dp[1005];memset(sum,0,sizeof(sum));memset(mx,0,sizeof(mx));memset(dp,0,sizeof(dp));for(int i=1; i<=n; ++i){cin >> num[i];sum[i] = sum[i-1] + num[i];}for(int i=1; i<=n; ++i){for(int k=i-1; k>=0; --k)//从后往前合并 {//k+1到i堆书合起来的高度大于等于前k堆最高的高度 if(sum[i]-sum[k] >= mx[k]){//k+1堆到i堆需要合并i-（k+1）次//dp[k]就是从第1堆到第k堆需要的合并次数    dp[i] = dp[k] + i-k-1;mx[i] = sum[i] - sum[k];break;//只需找到一次满足要求的k就行 }}}printf("Case %d: %d\n",cnt++,dp[n]);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！