题解 | #值钱的项链#

F题题解

思路

线性dp
(1)状态表示： 
 f[i][0]：长度为i且第i个珠子为蓝色时的最大价值，若第i个珠子不可以为蓝色，则值为负无穷
 f[i][1]：长度为i且第i个珠子为红色时的最大价值，若第i个珠子不可以为红色，则值为负无穷
 w[i][0]：第i个位置 蓝色珠子的最大价值，若无蓝色珠子则取负无穷代表取不到
 w[i][1]: 第i个位置 红色珠子的最大价值，若无红色珠子则取负无穷代表取不到

(2)集合划分
case 1：第一个珠子取红色时 
初始化：    f[1][1]=w[1][1] , f[1][0]=负无穷  
状态计算:   f[i][0]=max(f[i-1][1],f[i-1][0])+w[i][0] 
           f[i][1]=f[i-1][0]+w[i][1]

 => ans1 = f[n][0]

case 2：第一个珠子取蓝色时
初始化：   f[1][0]=w[1][0] , f[1][1]=负无穷
状态计算： f[i][0]=max(f[i-1][1],f[i-1][0])+w[i][0] 
          f[i][1]=f[i-1][0]+w[i][1]    

 => ans2 = max(f[n][0],f[n][1])

最后的结果是 max(ans1,ans2)

ps: 在进行分类讨论第1个珠子为红色还是蓝色 之前，我们需要进行特判：
   若 必存在两个红色珠子相邻的情况，输出 -1
   若 只有1个珠子即n=1时，输出 max(w[1][0],w[1][1])
   在特判之后 再进行分类讨论......

综上，Code 如下

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N=1e6+10;
const ll INF=-1e18; 

ll f[N][2];
ll w[N][2];
ll val[N];     // 珠子的价值
bool st[N][2]; // 用于看第i个位置是否有蓝色珠子和红色珠子
int n,m;

int main(){
    int T;
    scanf("%d",&T);

    while(T--){ 
        // 此处for循环不可以用memset代替,会超时
       for(int i=1;i<=n;i++) {
         f[i][1]=f[i][0]=0;
         w[i][1]=w[i][0]=-1e18;   
         st[i][1]=st[i][0]=false;
        }
        scanf("%d %d",&n,&m);

        int t=0;
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)  scanf("%lld",&val[++t]); 

        t=0;
        int flag=0;
        for(int i=1;i<=n;i++){
           for(int j=1;j<=m;j++)  {
               t++;
               int x;
               scanf("%d",&x);
               if(x)   w[i][1]=max(w[i][1],val[t]),st[i][1]=true; //第i个位置的红色最大值      
               else w[i][0]=max(w[i][0],val[t]),st[i][0]=true;  //第i个位置的蓝色最大值
           }  
           if(i>=2&&st[i][0]==false&&st[i-1][0]==false) flag=1;
        }
        if(st[1][0]==false&&st[n][0]==false) flag=1;

        if(n==1)     printf("%lld\n",max(w[1][0],w[1][1]));
        else if(flag) printf("-1\n");
        else {
             ll res=0;
            //第一个取红色时
            f[1][1]=w[1][1];
            f[1][0]=INF;    // 不可以等于0，必须极小代表取不到  
            for(int i=2;i<=n;i++){
               f[i][1]=f[i-1][0]+w[i][1];
               f[i][0]=max(f[i-1][1],f[i-1][0])+w[i][0];
             }
             res=f[n][0];

            // 第一个取蓝色时
            for(int i=1;i<=n;i++)  f[i][1]=f[i][0]=0;
            f[1][1]=INF;   // 不可以等于0，必须极小 
            f[1][0]=w[1][0];
            for(int i=2;i<=n;i++){
               f[i][1]=f[i-1][0]+w[i][1];
               f[i][0]=max(f[i-1][1],f[i-1][0])+w[i][0];
             }

            res=max(res,max(f[n][1],f[n][0]));
            printf("%lld\n",res);
        }   
    }
    return 0;
}