K题题解

方法：状态压缩DP——（视频）https://www.bilibili.com/video/BV1Uk4y117z1/?spm_id_from=333.337.search-card.all.click&vd_source=c13d187ae699de8a29dd35ec302e586f

dp的思想：dp一般用于解决多阶段决策问题，即每个阶段都要做一个决策，全部的决策是一个决策序列，要你求一个最好的决策序列使得这个问题有最优解.dp的每个决策之间有联系；

思路：盖子有三个状态左移右移和不动，状态压缩就是用数字来表示这些状态即不动0，左移-1，右移1； 接下来怎么写呢？

1.先写转移方程，即思考这一步等于这上一步加这步的最优解。

2.要保证相邻的盖子位置合法，这里就是 1.pos[i]+j>pos[i-1]+k

3.要知道 dp 的结束条件，这里就是枚举小于盖子数量 cnt 时； 4.要初始化 dp 数组，因为我们是由前面推到后面的。

设 dp[i][j] 表示 0--i 的位置为j的状态时的最好决策，j 是 i 时的盖子状态，k 是 i-1 时的盖子状态；

第一行代码是初始化**dp[1]**的三种状态

**pos[]**是盖子的初始位置，a[] 是盒子的值，k-1 ,是因为左移，位置变化所以是 -1--1

所以最后一步需要得到三个状态的最大值也就是最好决策

（ps：max函数的使用注意事项 max({a,b,c})是将三个数字放在一个数组里用max比较 状态压缩可能会用到的函数：std库里的函数__builtin_popcount(),直接返回十进制数字的二进制表示中的1的数字。）

#include<bits/stdc++.h>
const int N=1e6+10;
typedef long long ll;
ll a[N],b[N],pos[N],dp[N][3];//定义dp数组-1左移，0不动，1右移
int main(){
    ll n,cnt=0;
    std::cin>>n;
    for(int i=1;i<=n;i++){
        std::cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        std::cin>>b[i];
        if(b[i]) pos[++cnt]=i;//把有盖子的位置存下来
    }
    if(!cnt){
        std::cout<<"0";
        return 0;//一个盖子也没有，直接为0；
    }
    if(pos[1]>1) dp[1][-1]=a[pos[1]-1];//第一个盖子可以左移
    dp[1][0]=a[pos[1]];
    if(pos[1]<n) dp[1][1]=a[pos[1]+1];//可往右移动一个
    for(int i=1;i<=cnt;i++){
        for(int j=-1;j<=1;j++){//j是当前状态开始枚举上一个盖子的状态k
            for(int k=-1;k<=1;k++){
                if(pos[i]+j>pos[i-1]+k&&(pos[i]+j)<=n){//合法的时候
                    dp[i][j]=std::max(dp[i][j],dp[i-1][k]+a[pos[i]+j]);
                }
            }
        }
    }
    std::cout<<std::max({dp[cnt][-1],dp[cnt][0],dp[cnt][1]});//max({a,b,c})是将三个数字放在一个数组里用max比较
    return 0;
}