#include #include #include #include #include using namespace std; int n; vector note; vector > maxNote; vector > 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了，但是从这道题来看，难点还止于此，后处理工作仍然不容小觑。关于构造解，个人的观点是，思路虽然很简单，但是要想在短时间内说服别人却是不容易的。