Codeforces1091F. New Year and the Mallard Expedition
题目大意
有一段分为n段的路，有草地，水和岩浆。可以在草地上走，水里游泳，任何地形上飞，走1单位消耗5单位时间，获得1点能量；游泳消耗3单位时间，获得1点能量；飞消耗1单位时间，消耗1点能量，求走完这段路的最短时间。
题解
先假设在所有草地上走，在水中游泳，在岩浆上飞。
如果某一时刻需要飞而能量不足，可以在前面的某处反复移动获得能量，如果有水优先游泳。
如果最后能量过多，就需要将前面游泳或走的一段路变成飞，但必须保证不能在某个位置能量为负。
我们应该尽可能多的将走路转化成飞，从头开始维护这个值，显然不能超过草地的长度，因为不能出现能量为负的位置，还需要用当前能量/2更新这个值。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define ll long long using namespace std; ll read() { char ch=getchar();ll f=0,x=1; while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();} while(ch>='0'&&ch<='9'){f=(f<<1ll)+(f<<3ll)+ch-'0';ch=getchar();} return f*x; } char s[100005]; ll a[100005]; int n; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); scanf("%s",s+1); ll ans=0,now=0,temp=0;bool w=0; for(int i=1;i<=n;i++) { if(s[i]=='G') { ans+=5LL*a[i]; now+=a[i]; temp+=2LL*a[i]; } else if(s[i]=='W') { ans+=3*a[i]; now+=a[i]; w=1; } else { ans+=a[i]; now-=a[i]; if(now<0) { ans-=now*(w?3:5); now=0; } } temp=min(temp,now); } if(now>0) { ans-=2LL*temp; ans-=now-temp; } cout<<ans; } |