题目描述:
第一行 n (n<1000)
第二行n个数, 表示n个人入公司的年限.发工资的规则是这样的, 入职年限高的比入职年限低的工资高, 但所幸的是每一个人只会知道身边两人的工资情况.
问满足此情况的最少工资数.
样例:
输入1
4
1 2 3 2
输出1
700 (100, 200, 300)
输入2
6
1 3 3 3 2 1
输出2:
1300(100, 300, 300, 200, 100)
核心思想: 谷底(比身边两人入职年限都低的人)一定是100, 然在一个山峰周期内,从谷底向山峰增加, 峰顶是两端所增加的最大值
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=1e3+7; 4 int y[N], val[N]; 5 int n; 6 int main() 7 { 8 cin>>n; 9 for (int i=1;i<=n;i++) 10 cin>>y[i]; 11 int i=1; 12 while (1) { 13 int s=i; 14 while (i+1<=n&&y[i+1]>=y[i]) i++; // 上升到top 15 int top=i; 16 while (i+1<=n&&y[i+1]<=y[i]) i++; // 下降到i(谷底) 17 // 从山峰两端最低点上升 18 val[s]=100;// 谷底一定是100 19 for (int j=s+1;j<=top;j++) { // 左端谷底上升 20 if (y[j]==y[j-1]) 21 val[j]=val[j-1]; 22 else 23 val[j]=val[j-1]+100; 24 } 25 val[i]=max(100, val[i]); // 右端谷底上升, 山峰最高点取两端最大值 26 for (int j=i-1;j>=top;j--) 27 if (y[j]==y[j+1]) 28 val[j]=max(val[j], val[j+1]); 29 else 30 val[j]=max(val[j], val[j+1]+100); 31 int j=top-1; 32 while (y[j]==y[top]) // 山峰可能是平的, 不是尖的 33 val[j--]=val[top]; 34 if (i==n) 35 break; 36 } 37 int ans=0; 38 for (int i=1;i<=n;i++) { 39 //printf("%d\n",val[i]); 40 ans+=val[i]; 41 } 42 printf("%d\n",ans); 43 return 0; 44 }
原文：https://www.cnblogs.com/xidian-mao/p/11337961.html