topcoder13688CountryGroupHard

topcoder 13688 CountryGroupHard

题意:

有\(n\)个人坐在一排，每个人来自一个国家，来自相同国家的人坐在一起. 记者询问了每个人，“你的国家有多少人坐在这里？” 每个人都如实回答了. 答案序列为\(a\)，\(a_i\)即为第\(i\)个人的回答. 但档案丢失了一部分. 所以\(a_i\)要么为\(0\)，要么为一个正整数.

如果记者能通过档案还原所有丢失的部分，输出"Sufficient". 否则输出"Insufficient".

\(1\leq n\leq 100,0\leq a_i\leq n\)

保证至少有一组可行解.

题解:

如果通过直接判断是否只有一种情况，细节很多，不是很好做.

但如果只是判断当前是否存在一组解，稍微想想发现是很好做的，而且\(n\)很小，所以可以考虑给\(a_i=0\)的每个\(a_i\)从\(1\)赋值到\(n\)，如果不能确定的情况，必定对于某一个\(a_i\)，有两种及以上可行的取值. 现在枚举的时间复杂度是\(O(n^2)\).

接着，就是如何判断有可行解. 可以用\(f_i\)表示在第\(i\)个位置是否可以作为同一国家连续段的右端点.

分成两种情况

1.\(a_i\not=0\), \(f_i=f_{i-a_i}\).

2.\(a_i=0,f_i=f_{i-a_j}|f_{i-1}\)

此时，需要找到离\(a_i\)最近的\(a_j\not=0\)（这一步可以通过预处理实现），那么在第\(i\)位要么是长度为\(1\)连续段的右端点，要么就是长度为\(a_j\)的连续段的右端点. （因为对于其他长度来说，要么不合法，要么可以化成一些长度为\(1\)连续段）

每次预处理的时间复杂度是\(O(n)\)的，dp的时间复杂度也是\(O(n)\)的，再算上前面的枚举，总的时间复杂度是\(O(n^3)\).

时间复杂度: \(O(n^3)\)

空间复杂度: \(O(n^2)\)