题面描述
有 \(n\) 个箱子，第 \(i\) 个箱子里面装着 \(a_i\) 个杂志。现在正在下雨，有一些箱子上面盖着盖板（如果一个箱子上盖了盖板，那么这个箱子里的杂志就不会被雨淋），并且可以将盖在第 \(i\) 个箱子上的盖板移到第 \(i-1\) 个箱子上（同一个盖板至多移动一次）。求不会被雨淋的杂志数量的最大值。
思路
动态规划。定义 \(f_{i,0/1}\) 表示考虑到第 \(i\) 个箱子，\(0\) 表示板子不会被移走，\(1\) 表示板子会被移走，不会被雨淋得最大数量。
考虑转移方程。如果当前位置有盖子的话，\(f_{i,0}=max(f_{i-1,0},f_{i-1,1})+a_i\)。如果上一位没有板子的话，则是 \(f_{i,1}=f_{i-1,0}+a_{i-1}\),否则的话 \(f_{i,1}=f_{i-1,1}+a_{i-1}\)。如果当前没有板子的话，\(f_{i,0}=max(f_{i-1,0},f_{i-1,1})\)。
一道简单的 \(dp\) 题。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
const int maxn=2e5+5;
int qp(int a,int b){
int ans=1;
while(b){
if(b&1){
ans*=a;
ans%=mod;
}
a*=a;
a%=mod;
b>>=1;
}
}
int fac[1000005],inv[1000005];
void init(){
fac[0]=1;
for(int i=1;i<=1000000;i++){
fac[i]=fac[i-1]*i%mod;
}
inv[1000000]=qp(fac[1000000],mod-2);
for(int i=999999;i>=0;i--){
inv[i]=inv[i+1]*(i+1)%mod;
}
}
int C(int i,int j){
if(i<0||j<0||i<j) return 0;
return fac[i]*inv[j]%mod*inv[i-j]%mod;
}
int f[maxn][2];
char c[maxn];
int a[maxn];
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
scanf("%s",c+1);
for(int i=1;i<=n;i++){
cin>>a[i];
}
f[1][0]=f[1][1]=0;
if(c[1]=='1'){
f[1][0]=a[1];
}
for(int i=2;i<=n;i++){
if(c[i]=='1'){
f[i][0]=max(f[i-1][0],f[i-1][1])+a[i];
if(c[i-1]=='0'){
f[i][1]=f[i-1][0]+a[i-1];
}else{
f[i][1]=f[i-1][1]+a[i-1];
}
}else{
f[i][0]=max(f[i-1][0],f[i-1][1]);
f[i][1]=0;
}
}
cout<<max(f[n][1],f[n][0])<<endl;
}
return 0;
}