NOIP 2013 洛谷 P1969 积木大赛

题目：积木大赛

思路：
令f[i]表示建到第i列的最少次数。
转移：
$f[i]=f[i?1]+a[i]?a[i?1](a[i]>a[i?1])$
$f[i]=f[i?1](a[i]<a[i?1])$

代码：

#include<bits/stdc++.h>
using namespace std;#define maxn 100000
#define read(x) scanf("%d",&x);int n;
int a[maxn+5];
int f[maxn+5];int main() {
    read(n);for(int i=1;i<=n;i++) {
    read(a[i]);}for(int i=1;i<=n;i++) {
    if(a[i]>a[i-1]) f[i]=f[i-1]+a[i]-a[i-1];else f[i]=f[i-1];}printf("%d",f[n]);return 0;
}