CF803E Roma and Pokar
给定一个由 W,D,L,? 构成的长度为 \(n\) 的字符串，并给定一个常数 \(k\)，你要替换字符串中的所有 ?，使得原串的 W,L 出现次数之差的绝对值为 \(k\)，且除原串外任意前缀的 W,L 出现次数之差的绝对值小于 \(k\)，求构造出的字符串，无解输出 NO，否则输出构造后的字符串。
法一:差分约束
将等于 \(k\) ,小于 \(k\) 全部转化为差分约束.跑一遍spfa得解。难写,没有优化空间。
法2:DP \(O(n^2)\)
设 \(dp_{i,j}\) 表示对于字符串前 \(i\) 位, W , L 出现次数绝对值为 \(j\) 是否有解。\(dp_{0,0}\) 显然初始化为 true .则有如下转移方程:(设四种字符依次为 \(1,0,-1,2\) )
显然枚举 \(j\) 的范围是 \((-k,k)\) ,注意不要像某些题解一样访问数组负下标。
另外开一个数组记录某状态是由哪一状态转移过来的即可。
#include
#include
#include 法3: DP \(O(n)\)(大概是)
考虑优化,首先容易发现所有为 true 的dp数组必然在给定的 \(i\) 上形成连续段。这是由于初始为真的只有一个位置,而之后的每次更新都只会向上\下\上下平移 \(1\) 格,所以必然形成连续段。这样,每次只需要从之前保存的 \(i-1\) 时为真的dp数组的左右端转移即可。这样就做到几乎为 \(O(n)\) 的复杂度。具体比这高多少我并不会证。
据说还有更快的栈+贪心做法...
代码来自 @mig
#include
using namespace std;
pair w[2006];
int main() {
int n, k;
bool flag = false;
string s;
cin>> n >> k;
cin>> s;
s = " " + s;
for(int i = 1; i < n; i++) {
if(s[i] == 'W') {
w[i-1].first + 1 < k ? w[i].first = w[i-1].first + 1 : flag = true;
w[i-1].second + 1 < k ? w[i].second = w[i-1].second + 1 : w[i].second = w[i-1].second;
} else if(s[i] == 'L') {
w[i-1].first - 1 > -k ? w[i].first = w[i-1].first - 1 : w[i].first = w[i-1].first;
w[i-1].second - 1 > -k ? w[i].second = w[i-1].second - 1 : flag = true;
} else if(s[i] == 'D')
w[i].first = w[i-1].first, w[i].second = w[i-1].second;
else {
w[i-1].second + 1 < k ? w[i].second = w[i-1].second + 1 : w[i].second = w[i-1].second;
w[i-1].first - 1 > -k ? w[i].first = w[i-1].first - 1 : w[i].first = w[i-1].first;
}
if(flag)
return 0*puts("NO");
}
if(s[n] == 'W') {
w[n].first = w[n-1].first + 1;
w[n].second = w[n-1].second + 1;
} else if(s[n] == 'L') {
w[n].first = w[n-1].first - 1;
w[n].second = w[n-1].second - 1;
} else if(s[n] == 'D') {
w[n].first = w[n-1].first;
w[n].second = w[n-1].second;
} else {
w[n].first = w[n-1].first - 1;
w[n].second = w[n-1].second + 1;
}
if(w[n].first > -k && w[n].second < k)
return 0*puts("NO");
int j;
w[n].second == k ? j = k : j = -k;
for(int i = n; i > 0; i--) {
char c = s[i];
if(c == 'W')
j--;
else if(c == 'L')
j++;
else if(c == '?') {
if(j - 1 >= w[i-1].first)
s[i] = 'W', j--;
else if(j + 1 <= w[i-1].second)
s[i] = 'L', j++;
else
s[i] = 'D';
}
}
cout<< s.substr(1, n);
return 0;
}