这是在codeforces上参加的第二场比赛了，虽然最后测评的结果显示在房间排名是第二名，但是与第一名的差距之大却是很难看的。这里，简单地报告一下E题Summer Reading的两种解法。比赛完后，看了作者提供的tutorial仍然是一脸雾水，主要是因为误解block为输入中连续的数字块。之后，借鉴了牛人的代码，才知道block其实是指一本书号的数字块。如给定输入序列为0 0 2 2 3 3 0 0 4 4 0，这其中就存在着三个block，即2 2；3 3；4 ；而非两个block（2 2 3 3；4 ；）。
解法一（思想源于作者的tutorial）：
根据作者提供的DP思想，对于每一个block都可以尝试进行向左或向右扩展，如 4 可以向左扩展为 4 4 4 ，然后再向右扩展，就变为了 4 4 4 4 ，并且符号题中所给条件。对于一个特定的block[i]来说，其向左扩展的限制在于其左边的block[i-1]的向右扩展结果，block[i-1]与block[i]间缺少的书号，以及block[i-1]后面紧跟着的0的个数，而其向右扩展的限制在于其向左扩展的结果以及block[i]后面紧跟着的0的个数。
示例：0 0 2 2 3 3 0 0 4 0
block[1] = 2 2，此时已无法向左扩展（即向左扩展0位），因为必须block[1]之前缺少的书号的数目为1（即只有书号1缺失），至少要占据两个0。并且由于block[1]后面没有紧跟着的0，所以向右也无法扩展。
block[2] = 3 3，向左无法扩展，因为block[1]与block[2]之间没有0存在。向右可以扩展1位或者2位，都不会打破题中的限制。
block[3] = 4 4，向左扩展讨论：在block[2]扩展1位的情况下，block[3]向左扩展1位；在block[2]扩展2位的情况下，block[3]向左无扩展（即扩展0位）。向右扩展讨论：在block[3]向左扩展1位或者2位的情况下，block[3]向右扩展1位，或者不扩展。
在block[3]向左不扩展时，block[4]向右扩展1位。
在上述block扩展的过程中，如果有一个block不管是向右扩展几位（包括扩展0位）都无法满足题中条件时，就直接输出-1，并退出执行。否则，就可以利用block的扩展情况进行还原书号序列。
下面用两个数组exLeft和exRight来分别表示每个block的向左扩展情况和向右扩展情况。为了方便，令block[1]之前还存在着一个block[0]。
block[0]：为了不占用block[0]后面的零，令exRight[0][0]= true，exRight[0][1-4] = false
block[1]：exLeft[1][0] = true，exLeft[1][1-4]= false（block[1]无法向左扩展）；同理，exRight[1][0]= true，exRight[1][1-4] = false。
block[2]：exLeft[2][0] = true，exLeft[2][1-4]= false；exRight[2][0-2] = true，exRight[2][3-4]= false（block[2]向右扩展1位或者2位均可）。
block[3]：exLeft[3][0-1] = true，exLeft[3][2-4]= false；exRight[3][0-1] = true，exRight[3][2-4]= false（exRight[3][0] = true对应于exLeft[3][1]= true，而exRight[3][1] = true对应于exLeft[3][0]= true或者exLeft[3][1] = true）。
对于最后一个block，为了使得留出更多的0来填充更大的书号，我们要使用exRight[3][i] = true最小的那个i，即i= 0，但由于此时只剩下一个0，无法完整填充更大的书号，所以i=1。接着寻找可以与exRight[3][1]= true相对应的exLeft[3][j]，然后利用exLeft[3][j]找到可以与其相对应的exRight[2][k]，如此递归下去。对于每个block，利用找到的合适的exLeft和exRight进行向左、向右扩展，完成书号的填充。
在编码过程中，exLeft[i][j]里面可以记录可以与其相对应的一个exRight[i-1][k]中的k值，这样就可以快速向前递归填充了。
代码：
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
class BLOCK {
public:
int elem;
int numElem;
int numZero;
public:
BLOCK(int _elem = 0, int _numElem = 0, int _numZero = 0)
{
elem = _elem;
numElem = _numElem;
numZero = _numZero;
}
};
int n;
vector<int> note;
vector<BLOCK> block;
vector<vector<int> > toLeft, toRight;
vector<int> ans;
bool Work()
{
block.clear();
block.push_back( BLOCK(0,0,0) );
for(int i = 0; i < n; ++i)
{
if( !note[i] )
{
block.back().numZero++;
}
else
{
if( note[i] != block.back().elem )
{
block.push_back( BLOCK(note[i], 1, 0) );
}
else
{
block.back().numElem += block.back().numZero + 1;
block.back().numZero = 0;
}
}
}
toLeft.assign(block.size(), vector<int>(5,-1));
toRight.assign(block.size(), vector<int>(5,-1));
toRight[0][0] = 0;
for(int i = 1; i < int(block.size()); ++i)
{
// calculate toLeft[i], which is only related to toRight[i-1]
for(int l = 0; l < 5; ++l)
{
if( l + block[i].numElem > 5 ) continue;
for(int r = 0; r < 5 && toLeft[i][l] < 0; ++r)
{
if( toRight[i-1][r] < 0 ) continue;
if( r + l <= block[i-1].numZero )
{
int zeros = block[i-1].numZero - l - r;
int diff = block[i].elem - block[i-1].elem;
diff -= 1;
if( zeros >= diff*2 && zeros <= diff*5 )
{
toLeft[i][l] = r;
}
}
}
}
// calculate toRight[i], which is only related to toLeft[i]
bool terminal = false;
for(int r = 0; r < 5; ++r)
{
if( r > block[i].numZero ) continue;
for(int l = 0; l < 5 && toRight[i][r] < 0; ++l)
{
if( toLeft[i][l] < 0 ) continue;
int num = r + l + block[i].numElem;
if( num >= 2 && num <= 5 )
{
toRight[i][r] = l;
terminal = true;
}
}
}
if( !terminal )
return false;
}
int size = int(block.size());
int pos = 0;
while( toRight[size-1][pos] < 0 && pos < 5 ) ++pos;
int remain = block.back().numZero - pos;
ans.clear();
if( remain == 1 )
{
++pos;
if( toRight[size-1][pos] < 0 )
return false;
ans.push_back( block.back().elem );
}
else if( remain > 1 )
{
int val = block.back().elem + 1;
if( remain&1 )
{
ans.push_back( val );
--remain;
}
for(int i = 1; i <= remain; ++i)
{
ans.push_back( val );
if( !(i&1) )
++val;
}
reverse(ans.begin(), ans.end());
}
int lj, rj = pos;
for(int i = size - 1; i > 0; --i)
{
lj = toRight[i][rj];
int num = lj + rj + block[i].numElem;
for(int k = 0; k < num; ++k)
ans.push_back( block[i].elem );
rj = toLeft[i][lj]; // cal the position, to which (i-1)th block extends;
int zeros = block[i-1].numZero - rj - lj;
int numVal = block[i].elem - block[i-1].elem - 1;
if( !numVal ) continue;
vector<int> temp;
int m = zeros/numVal, re = zeros%numVal;
int val = block[i-1].elem + 1;
for(int k = 1; k <= numVal; ++k)
{
for(int j = 0; j < m; ++j)
temp.push_back( val );
if( k <= re )
temp.push_back( val );
++val;
}
reverse(temp.begin(), temp.end());
ans.insert(ans.end(), temp.begin(), temp.end());
}
reverse(ans.begin(), ans.end());
cout << ans.back() << endl;
for(int i = 0; i < int(ans.size()); ++i)
cout << ans[i] << " ";
cout << endl;
return true;
}
int main()
{
ios::sync_with_stdio(false);
//freopen("data.tst", "r", stdin);
while( cin >> n )
{
note.resize( n );
for(int i = 0; i < n; ++i)
cin >> note[i];
if( !Work() )
cout << -1 << endl;
}
return 0;
}
解法二：构造解
把Vasya做n天的SummerReading想象成骑车穿过n米的长路。那么Vasya最快的方式是每隔两米，速度就增加1，最慢的方式是每隔五米，速度才增加1。输入中的非零数代表Vasya在此点时的速度。如果这个非零值小于Vasya以最慢的方式达到此点的速度，或者大于Vasya以最快的方式达到此点的速度，那么肯定是不合法的。
示例：0 0 2 2 3 3 0 0 4 4 0
最快方式：1 1 2 2 3 3 4 4 4 4 5
最慢方式：1 1 2 2 3 3 4 4 4 4 4
根据题中要求对于出现的书号，至少要出现两次。所以，对于达到的速度值至少要出现两次。最快的方式里面5只出现一次，为了满足条件，必须减1。最快方式就变成了 1 1 2 2 3 3 4 4 4 4 4。然后，利用最快方式的速度序列，从后往前把给定的原速度序列进行恢复即可。
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstdlib>
using namespace std;
int n;
vector<int> note;
vector<pair<int,int> > maxNote;
vector<pair<int,int> > minNote;
bool Work()
{
maxNote.resize( n );
minNote.resize( n );
maxNote[0] = make_pair(1, 1);
minNote[0] = make_pair(1, 1);
if( note[0] > 1 )
return false;
for(int i = 1; i < n; ++i)
{
if( maxNote[i-1].second < 2 )
maxNote[i] = make_pair(maxNote[i-1].first, maxNote[i-1].second + 1);
else maxNote[i] = make_pair(maxNote[i-1].first+1, 1);
if( minNote[i-1].second < 5 )
minNote[i] = make_pair(minNote[i-1].first, minNote[i-1].second + 1);
else minNote[i] = make_pair(minNote[i-1].first+1, 1);
if( note[i] )
{
if( note[i] > maxNote[i].first || note[i] < minNote[i].first )
return false;
if( note[i] < maxNote[i].first )
maxNote[i] = make_pair(note[i], 5);
if( note[i] > minNote[i].first )
minNote[i] = make_pair(note[i], 1);
}
}
if( maxNote[n-1].second == 1 )
maxNote[n-1] = maxNote[n-2];
if( note[n-1] > maxNote[n-1].first )
return false;
return true;
}
int main()
{
//freopen("data.tst", "r", stdin);
while( cin >> n )
{
note.resize( n );
for(int i = 0; i < n; ++i)
cin >> note[i];
bool ans = Work();
if( !ans )
{
cout << -1 << endl;
continue;
}
note[n-1] = maxNote[n-1].first;
int len = 1;
for(int i = n - 2; i >= 0; --i)
{
if( maxNote[i].first >= note[i+1] )
{
note[i] = note[i+1];
++len;
if( len > 5 )
{
--note[i];
len = 1;
}
}
else
{
note[i] = maxNote[i].first;
len = 1;
}
}
cout << note[n-1] << endl;
for(int i = 0; i < n; ++i)
cout << note[i] << " ";
cout << endl;
}
return 0;
}
总结：算法题总是一题多解的，以前总是认为对于DP算法题，只要找出最优子结构，然后列出递推公式就ok了，但是从这道题来看，难点还止于此，后处理工作仍然不容小觑。关于构造解，个人的观点是，思路虽然很简单，但是要想在短时间内说服别人却是不容易的。