D.money
贪心，直接贴官方的题解吧。
题目大意
你要按照顺序依次经过n个商店，每到达一个商店你可以购买一件商品，也可以出售你手中的商品。 同一时刻你手上最多拿一件商品。在第i个商店购买和出售的代价都是a[i]。 问你经过完n个商店后的最大收益。 同时，在最大化收益的前提下，求最小的交易次数。
做法
DP
f[i][0/1]表示已经访问完了i个商店，你手中是否有商品，此时的最大收益。 g[i][0/1]表示当f[i][j]取最大值时最少的交易次数。
贪心
首先，如果a[i]=a[i+1]，则可以删掉第i+1个商店。因为任何在第i+1个商店进行的交易都可以转为在第i个商店 进行，且收益不变。之后，如果a[i]<a[i+1]，则离开第i个商店时一定要带上一件商品。如果a[i]>a[i+1]，则离开 第i个商店时一定要空着手。这样，第一问的答案就为
，第二问的答案就为长度>1的 极大递增连续段的数量。
反正贪心就可以，按队友思路写的代码:
1 //D-贪心 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 #include<queue> 8 #include<stack> 9 #include<map> 10 #include<cctype> 11 #include<cstdlib> 12 13 typedef long long ll; 14 const int maxn=1e5+10; 15 const int inf=0x3f3f3f3f; 16 const int mod=1e9+7; 17 const double eps=1e-5; 18 ll a[maxn]; 19 20 int main() 21 { 22 int t; 23 scanf("%d",&t); 24 while(t--){ 25 int n; 26 scanf("%d",&n); 27 for(int i=0;i<n;i++) 28 scanf("%lld",&a[i]); 29 a[n]=-1; 30 ll sum=0,minn=a[0],maxx=a[0]; 31 int num=0,i=0; 32 while(1){ 33 i++; 34 if(i>n)break; 35 if(a[i]<maxx){ 36 if(maxx!=minn) num+=2; 37 sum+=maxx-minn; 38 maxx=minn=a[i]; 39 } 40 maxx=std::max(maxx,a[i]); 41 } 42 printf("%lld %d\n",sum,num); 43 } 44 }
牛客网暑期ACM多校训练营（第二场）D.money-贪心 or dp
原文：https://www.cnblogs.com/ZERO-/p/9359346.html