P9344 题解

首先设 f i f_i fi​ 为扫第 $1\sim i$ 中所有台阶所花最小代价。

易得转移方程：
f i = min ⁡ 0 ≤ j < n , c j + 1 = c i ( f j + a j + 1 + a i ) f_i = \min_{0 \leq j < n,c_{j+1}=c_i}(f_j + a_{j+1} + a_i) fi​=0≤j<n,cj+1​=ci​min​(fj​+aj+1​+ai​)
其中 f 0 = 0 f_0 = 0 f0​=0（即一个都没扫）。

仔细观察，可把 a i a_i ai​ 移到外面：
f i = min ⁡ 0 ≤ j < n , c j + 1 = c i ( f j + a j + 1 ) + a i f_i = \min_{0 \leq j < n,c_{j+1}=c_i}(f_j + a_{j+1}) + a_i fi​=0≤j<n,cj+1​=ci​min​(fj​+aj+1​)+ai​
发现 min ⁡ 0 ≤ j < n , c j + 1 = c i ( f j + a j + 1 ) \displaystyle \min_{0 \leq j < n,c_{j+1}=c_i}(f_j + a_{j+1}) 0≤j<n,cj+1​=ci​min​(fj​+aj+1​) 可以维护。

令 x 0 = min ⁡ 0 ≤ j < n , c j + 1 = 0 ( f j + a j + 1 ) , x 1 = min ⁡ 0 ≤ j < n , c j + 1 = 1 ( f j + a j + 1 ) \displaystyle x0 = \min_{0 \leq j < n,c_j + 1 = 0}(f_j + a_{j + 1}),x1 = \min_{0 \leq j < n,c_j + 1 = 1}(f_j + a_{j + 1}) x0=0≤j<n,cj​+1=0min​(fj​+aj+1​),x1=0≤j<n,cj​+1=1min​(fj​+aj+1​)，则：
f i = { x 0 + a i , if  c i = 0 x 1 + a i , otherwise. f_i = \begin{cases} x0 + a_i,& \text{if }c_i = 0 \\ x1 + a_i,& \text{otherwise.} \end{cases} fi​={x0+ai​,x1+ai​,​if ci​=0otherwise.​

代码如下：

#include 
#define ll long long
using namespace std;const int N = 2000005;
int n;
ll a[N],f[N];
bool c[N];int main()
{int t;scanf("%d",&t);while(t--){int i;scanf("%d",&n);for(i = 1;i <= n;i++)scanf("%lld",&a[i]);for(i = 1;i <= n;i++)scanf("%d",&c[i]);ll x0,x1;if(!c[1])x0 = a[1],x1 = 0x3ffffffffffffff;elsex1 = a[1],x0 =0x3ffffffffffffff;for(i = 1;i <= n;i++){ll t;if(!c[i])t = x0;elset = x1;f[i] = t + a[i];//转移if(!c[i + 1])//更新 x0,x1x0 = min(x0,f[i] + a[i + 1]);elsex1 = min(x1,f[i] + a[i + 1]);  }printf("%lld\n",f[n]);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！