```#include<iostream>
#include<cstdio>
using namespace std;
int n,x,y,ans;
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&x);
ans+=y>x?0:x-y,y=x;
}
printf("%d",ans);
return 0;
}```

## D1T2:money（货币系统）

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[25001],n,t;
bool v[25001];
int main(){
scanf("%d",&t);
while (t--){
memset(v,0,sizeof(v));v[0]=true;
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
int maxn=a[n],num=0;
for (int i=1;i<=n;i++)
if (v[a[i]]) num++;
else
for (int j=a[i];j<=maxn;j++)
if (v[j-a[i]]) v[j]=true;
printf("%d\n",n-num);
}
return 0;
}```

## D1T3:track（赛道修建）

DP维护两个值，一个是在以i为根节点的子树中能够选取的最多的长度大于等于c的链的数量，记为f[i]

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define N 50001
#define M 100001
int hd[N],nx[M],e[M],w[M];
int f[N],g[N],q[N];
int n,m,num=0;
void dfs(int x,int y,int c){
multiset<int> h;
vector<int> q;
f[x]=g[x]=0;
for (int i=hd[x];i;i=nx[i])
if (e[i]!=y){
dfs(e[i],x,c);
f[x]+=f[e[i]];
if (g[e[i]]+w[i]>=c) f[x]++;
else{
q.push_back(g[e[i]]+w[i]);
h.insert(g[e[i]]+w[i]);
}
}
sort(q.begin(),q.end());
vector<int>::iterator i;
multiset<int>::iterator j;
for (i=q.begin();i!=q.end();i++)
if (h.count(*i)){
h.erase(h.find(*i));
j=h.lower_bound(c-*i);
if (j==h.end()) g[x]=*i;
else{
f[x]++;
h.erase(j);
}
}
}
bool check(int c){
dfs(1,1,c);
return (f[1]>=m);
}
int main(){
int x,y,z,l=2146483647,r=0,ans=0;
memset(hd,0,sizeof(hd));
scanf("%d%d",&n,&m);
for (int i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
nx[++num]=hd[x],hd[x]=num,e[num]=y,w[num]=z;
nx[++num]=hd[y],hd[y]=num,e[num]=x,w[num]=z;
if (z<l) l=z;
r+=z*2;
}
while (l<r){
int mid=(l+r)>>1;
if (check(mid)) l=mid+1,ans=mid;
else r=mid,ans=mid-1;
}
printf("%d\n",ans);
return 0;
}```