题意:有n(1<=n<=5000)个塔,高度为hi,把当前塔放到相邻两个塔(如果存在的话)上的花费为1,问最少需要多少花费能组成不降的序列。
题解:开始想贪心,因为要保证最后面的一个区域内的塔高和最小,贪心到最后可能会有剩余塔高不足的情况,这样如果把它们放到最后一堆就wa了。
想tower[i]表示到达 i 塔时最后一堆的最小高度,dp[i]表示对应的最小花费。
Sure原创,转载请注明出处
#include <iostream> #include <cstdio> #include <memory.h> using namespace std; const int maxn = 5002; int tower[maxn],sum[maxn],dp[maxn]; int n; void read() { memset(dp,0,sizeof(dp)); tower[0] = sum[0] = 0; for(int i=1;i<=n;i++) { scanf("%d",&tower[i]); sum[i] = sum[i-1] + tower[i]; } return; } void solve() { for(int i=1;i<=n;i++) { for(int j=i-1;j>=0;j--) { if(sum[i] - sum[j] >= tower[j]) { tower[i] = sum[i] - sum[j]; dp[i] = dp[j] + i - j - 1; break; } } } printf("%d\n",dp[n]); return; } int main() { while(~scanf("%d",&n)) { read(); solve(); } return 0; }