빌딩 을 장식 하 다
현재 n 의 배열 이 있다.f [i] 를 설정 하면 i 를 마지막 으로 하 는 최 장 상승 서브 시퀀스 를 표시 합 니 다.f 배열 의 n - 1 항 을 지정 합 니 다.
곰 곰 이 생각 하 다
우선, 우 리 는 어떤 f 배열 이 n 의 배열 에 대응 할 수 있 는 지 알 아야 한다.DP 에 따 르 면 임의의 j 에 대해 쉽게 알 수 있 습 니 다.
선형 알고리즘
먼저 무 해 를 판단 한다. 만약 에 두 곳 의 차 가 1 이 생기 면 무 해 를 한다. 예 를 들 어 1, 3, 5 에 한 곳 의 차 가 2 와 이상 이 생기 면 무 해 를 한다. 예 를 들 어 1, 4 가 있 으 면 해 가 있 는 상황 은 1, 차이 가 없다 는 것 이다.2. 한 군데 만 모자라다.두 가지 상황 으로 나 누 어 토론 한다. 차이 가 없 는 사람 에 대해 서 는 어느 사람 이 빠 졌 는 지 직접 매 거 하고 무 거 운 것 을 판단 하면 한 사람 앞 에 똑 같은 요 소 를 채 우지 못 하도록 강제 하면 된다.1 이 모자 란 곳 은 이 자리 앞의 합 법 적 인 위치 에 차 수 를 채 우 면 된다.
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int maxn=1000000+10;
int b[maxn],pre[maxn];
bool bz[maxn];
int i,j,k,l,r,t,n,m,id;
ll ans;
int main(){
freopen("building.in","r",stdin);freopen("building.out","w",stdout);
scanf("%d",&n);
fo(i,1,n-1) scanf("%d",&b[i]);
pre[0]=0;
fo(i,1,n-1) pre[i]=max(pre[i-1],b[i]);
t=0;
fo(i,0,n-2)
if (b[i+1]>pre[i]+1) t+=b[i+1]-pre[i]-1;
if (t>1){
printf("0
");
return 0;
}
else if (t==1){
fo(i,0,n-1)
if (b[i+1]>pre[i]+1) break;
t=b[i+1]-1;
fo(i,0,n-1){
if (pre[i]==t-1) ans++;
if (b[i+1]>pre[i]+1) break;
}
printf("%lld
",ans);
return 0;
}
fo(i,0,n-1){
if (i==n-1){
ans+=(ll)pre[n-1]+1;
break;
}
l=1;r=pre[i]+1;
ans+=(ll)(r-l+1);
if (l<=b[i+1]&&b[i+1]<=r) ans--;
}
printf("%lld
",ans);
fclose(stdin);fclose(stdout);
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
