原题传送门:http://codeforces.com/problemset/problem/229/D
The city of D consists of n towers, built consecutively on a straight line. The height of the tower that goes i-th (from left to right) in the sequence equals hi. The city mayor decided to rebuild the city to make it beautiful. In a beautiful city all towers are are arranged in non-descending order of their height from left to right.
The rebuilding consists of performing several (perhaps zero) operations. An operation constitutes using a crane to take any tower and put it altogether on the top of some other neighboring tower. In other words, we can take the tower that stands i-th and put it on the top of either the (i - 1)-th tower (if it exists), or the (i + 1)-th tower (of it exists). The height of the resulting tower equals the sum of heights of the two towers that were put together. After that the two towers can't be split by any means, but more similar operations can be performed on the resulting tower. Note that after each operation the total number of towers on the straight line decreases by 1.
Help the mayor determine the minimum number of operations required to make the city beautiful.
The first line contains a single integer n (1 ≤ n ≤ 5000) — the number of towers in the city. The next line contains n space-separated integers: the i-th number hi (1 ≤ hi ≤ 105) determines the height of the tower that is i-th (from left to right) in the initial tower sequence.
Print a single integer — the minimum number of operations needed to make the city beautiful.
5 8 2 7 3 1
3
3 5 2 1
2
分析:
dp(i)表示对前i座塔进行操作后形成非递减序列所需要的最小操作步数
last(i)表示在dp(i)最小的前提下,第i座塔的最低高度。
易知,将[i,j]区间内的塔合并成一座需要j-i步
于是我们得到dp方程:dp(i)=max{dp(j)+i-j+1| j<i, h(j+1)+h(j+2)+...+h(i-1)+h(i) <= last(j)}
注意,我们在递推的过程中要同时记录、更新last(j)的值来确保得到最优解。
#include <cstdio> using namespace std; int dp[5010],sum[5010],last[5010]; int main() { int n; scanf("%d",&n); for(int i = 1;i <= n;i++){ int a; scanf("%d",&a); sum[i] = sum[i-1]+a; dp[i] = last[i] = 1<<30; } for(int i = 1;i <= n;i++){ for(int j = 0;j < i;j++){ if(sum[i]-sum[j] >= last[j] && dp[i] >= dp[j]+i-j-1){ dp[i] = dp[j]+i-j-1; last[i] =sum[i]-sum[j]>last[i]?last[i]:sum[i]-sum[j]; } } } printf("%d\n",dp[n]); return 0; }
相关推荐
Codeforces 1925D Good Trip 题解
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Educational Codeforces Round 157D. XOR Construction
【并查集】Codeforces 566D Restructuring Company题面在这里对于本题,只需要再维护一个并查集表示i所在联通块的最右位置因为相邻
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 149 D-Coloring Brackets,动态规划求解
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
Codeforces round 678 D2_Codeforces_源码
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
打codeforces的神器
codeforces-js Codeforces JS
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
Codeforces Round #723 (Div. 2).md