[ARC153C] ± Increasing Sequence
構造嚴格遞增的X序列,通過差分,可變?yōu)闃嬙烊珵檎腨(首項除外)。
推公式可知,Y需要滿足與B的內(nèi)積為0,其中B是A的后綴和。
因A取值特殊,故B有一定性質。其中:若B有正有負,則一定有+1和-1。
先考慮B有正有負的情況:
先讓Y全部為1,再看B的和 tot,+1的點可補償tot<0情況,-1的點可補償tot>0情況。
再考慮B無正整、或無負數(shù)情況:
因B不可能全0,所以一定需要補償,而只有無約束的Y[1]能起到補償?shù)淖饔茫?/p>
若B[1]為零,Y[1]不能發(fā)揮作用,無解,輸出"No"。
若B[1]非零,則設Y[2...n]都為B[1]的絕對值,再安排Y[1]來補償所有。
標簽: