JOISC2015 E. ビルの飾りつけ 3

Difficulty:None

問題

最長増加部分列DPをしたあとのDPテーブルから一個要素を消したものが与えられるので、もとのDPテーブルが何通りか求めよ

解法

最大値+1より大きくなるような位置が2箇所以上ある場合構築不可。

最大値+2より大きくなるような位置が存在する場合も構築不可。

1箇所のみの場合、その前の最大値が出た場所からそこまでの距離が答え（語彙力）

そうでない場合、それぞれの位置で累積最大値+1通り選べる。ただ重複がめんどいが、ぐっとにらむとn-2を答えから引けばよいことがわかる。（？？？？？）

実装

code:cpp

bool solve(){

LL(n);

vector<ll>a(n-1);

cin >> a;

ll cn{};

ll mx{},pos{-1},ans{};

rep(i,n-1){

cn++;

ans = i-pos;

}

cn = INF;

}

pos = i;

}

}

if(cn>1){

O(0);

deb("^^");

return false;

}

if(cn==1){

O(ans);

deb("--");

return false;

}

mx = -1;

rep(i,n-1){

ans += mx+1;

}

ans += mx+1;

ans -= n-2;

O(ans);

return false;

}