中文题 简单搜索题
例数据
输入 6
1 1 1 1 9 9
输出 3
注意是每一个递归搜索都返回一个min 而不是只有总的返回min
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; int a[5678]; int dfs(int l,int r,int k) { if(l>r||(l==r&&a[l]<=k)) return 0; if(l==r) return 1; //注意区间左闭右开 只有这里r+1考虑右边界 int mn=min_element(a+l,a+r+1)-a; //注意-k return min(r-l+1,dfs(l,mn-1,a[mn])+dfs(mn+1,r,a[mn])+a[mn]-k); } int main() { int n; while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof(a)); for(int i=0;i<n;i++) scanf("%d",&a[i]); //区间严格[l,r] //如果用0,n注意所有地方都要改 printf("%d ",dfs(0,n-1,0)); } return 0; }
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; int n,a[100005]; int get(int l,int r) { int minn=1e9+3; for(int i=l;i<=r;i++) { minn=min(minn,a[i]); } int ans=minn; for(int i=l;i<=r;i++) { if(a[i]==minn) continue; int ii=i+1; while(ii<=r&&a[ii]!=minn) ii++; ii--; for(int j=i;j<=ii;j++) a[j]-=minn; ans+=get(i,ii); i=ii; } return min(r-l+1,ans); } int main() { //freopen("in.txt", "r", stdin); while(~scanf("%d",&n)) { for(int i=0;i<n;i++) { scanf("%d",&a[i]); } printf("%d ",get(0,n-1)); } return 0; }