[BZOJ3043]IncDec Sequence
转载请注明出处：http://danihao123.is-programmer.com/
这题并不很好下手，但注意差分序列的前缀和为原值这个性质。
由此可见，所求数列的差分序列除了第一项以外都应该是0，求出满足条件的最小操作次数就轻松多了。
求满足条件的数列个数似乎也不是难事。通过差分序列易推数列第一项差分值的范围，突破口就在于此。
看起来，满足条件数列个数为[tex]max(S1,S2)-min(S1,S2)[/tex]（S1，S2分别为正、负差分绝对值的和）。但是请注意，存在第一项没被操作的特殊情况。并且精度也是个问题！
/**************************************************************
Problem: 3043
User: danihao123
Language: C++
Result: Accepted
Time:292 ms
Memory:820 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int n;
long long last=0,temp;
register long long S1=0,S2=0,i,cf,ans2;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%llu",&temp);
cf=temp-last;
if(i!=1){
if(cf>0)
S1+=cf;
else
S2-=cf;
}
last=temp;
}
ans2=max(S1,S2)-min(S1,S2)+1;
printf("%llu\n%llu\n",max(S1,S2),ans2);
return 0;
}
Jul 01, 2023 06:04:11 PM
Initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen journalists with diverse range of interest in Journalism who are passionate about publishing emodelpapers.in the Education Updates with transparency in general public interest.is a initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen journalists with diverse range of interest.