Year2008 #POI #贪心 #数学
考虑枚举旋转了几次,维护一个前缀和,一个前缀和的 \(min\) ,目标为使和合法并使前缀 \(min\) 满足条件,这个代价就可以 \(\mathcal{O}(1)\) 计算
// Author: xiaruize
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e6 + 10;
int n, p, q, x, y;
char s[N];
int a[N], mi[N];
int dp[N];
void solve()
{
cin >> n >> p >> q >> x >> y;
cin >> (s + 1);
rep(i, 1, n)
{
if (s[i] == '-')
a[i] = -1;
else
a[i] = 1;
a[i] += a[i - 1];
}
rep(i, 1, n) mi[i] = min(mi[i - 1], a[i]);
int d = (q - p - a[n]) / 2;
int res = INF;
rep(i, 1, n)
{
int cur = max(0, (-p - min(a[n] - a[n - i + 1] + mi[n - i + 1], dp[i - 1]) + 1) / 2);
res = min(res, (i - 1) * y + (cur + abs(d - cur)) * x);
dp[i] = min(dp[i - 1] + a[n - i + 1] - a[n - i], 0);
}
cout << res << endl;
}
#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int testcase = 1;
// cin >> testcase;
while (testcase--)
solve();
#ifndef ONLINE_JUDGE
cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
return 0;
}
标签:POI2008BBB,const,min,int,res,mi,BBB,dp
From: https://www.cnblogs.com/xiaruize/p/18136783