[NOIP2018 提高组] 铺设道路 贪心证明

标签：... ch int NOIP2018 铺设 序列 cases 贪心

首先，这个是本蒟蒻第一次正经证明贪心，方法肯定有些繁琐（知识有限），仅作纪念。

证明：

• 记\(f(x)\)为序列中从第\(1\)到第\(x\)个数满足题意的最小天数。
  对于非上升序列\(\{a_1,a_2,a_3,...,a_n\}\)

\[f(1)=a_1,f(2)=a_2+(a_1-a_2)=a_1,f(3)=a_3+(a_2-a_3)+[a_1-a_3-(a_2-a_3)]=a_1 \]

故猜测$$f(x)=a_x+(a_{x-1}-a_x)+[a_{x-2}-a_x-(a_{x-1}-a_x)]+...=a_1$$
记

\[g(x)=\begin{cases}a_x-g(x+1)-g(x+2)-...&x\leqslant n\\0&x>n\end{cases} \]

\(\therefore f(x)=\sum\limits_{i=1}^ng(i)=a_1-g(2)-g(3)-...-g(n-1)-g(n)+g(2)+g(3)+...+g(n-1)+g(n)=a_1\)

• 对于非上升序列\(\{a_1,a_2,a_3,...,a_n\}\)，加入一个元素\(a_{n+1}>a_n\)得\(\{a_1,a_2,a_3,...,a_n,a_{n+1}\}\)
  同上处理第一步得 \(\{a_1-a_n,a_2-a_n,a_3-a_n,...,0,a_{n+1}-a_n\}\)
  对此\(f(n)=a_1-a_n\)
  \(\therefore f(n+1)=f(n)+a_{n+1}-a_n\)

• 第二点中得到的新序列等价于一个非上升序列（首元素为\(a_1\)，尾元素为\(a_{n+1}\)），那么此后的处理任然按第一或二点实行，始终保持一个非上升序列。所以得出：

\[f(x)=\begin{cases}f(x-1)&a_x\leqslant a_{x-1}\\f(x-1)+a_x-a_{x-1}&a_x>a_{x-1}\end{cases} \]

感觉还可以用递推做（。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
namespace IO{
	char ibuf[(1<<20)+1],*iS,*iT;
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	#define reg register
	inline long long read(){
		reg char ch=gh();
		reg long long x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
}
using IO::read;//辟邪の代码
const int N=100000+10, INF=0x3f3f3f3f;
int n;
int a[N];
int maxn;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	maxn=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]>a[i-1]){
			maxn+=(a[i]-a[i-1]);
		}
	}
	cout<<maxn<<endl;
	return 0;
}
/*
今天你AC了几题?
不要颓废！！！！
Dalao has AKed IOI several times!!!
*/

标签：...,ch,int,NOIP2018,铺设,序列,cases,贪心
From： https://www.cnblogs.com/FaceLuck/p/16792943.html