题目链接

https://vjudge.net/contest/397650#problem/A
https://nanti.jisuanke.com/t/48301

解题思路

简单dp+简单贪心，甚至不能算贪心。
S1：先用dp[i]存，在不算特殊区间的情况下，前i个位置染色的最大值；
S2：对pos的all赋值，pos[i].all表示区间左端点为i的特殊区间全涂为自己特定颜色的情况下，此区间为不加额外美感情况下，涂为纯色的美观度；
S3：比较每一段特殊区间涂为纯色的美观度和dp数组中此区间的美观度比较，若前者大，就把此区间换成纯色，反之不变。

AC代码

//题目：https://vjudge.net/contest/397650#problem/A
//题解： 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+100;
struct P{
    int t;
    ll to,c,all;
}pos[N];
ll ans;
ll dp[N];
int n,m;
ll b[N],w[N];
void Input(){
    cin>>n>>m;
    memset(pos,0,sizeof pos);
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=m;i++) {
        int t,l,r;
        ll c;
        cin>>t>>l>>r>>c;
        pos[l].t=t;
        pos[l].to=r;
        pos[l].c=c;
    }
} 
void BuildDP(){
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1]+max(b[i],w[i]);
    }
    ans=dp[n];
}
void BuildPos(){
    for(int i=1;i<=n;i++){
        int now=i;//勿忘！ 
        if(pos[now].t==1) {
            for(;i<=pos[now].to;i++)
                pos[now].all+=b[i];
            i--;//勿忘！ 
        }
        else if(pos[now].t==2){
            for(;i<=pos[now].to;i++)
                pos[now].all+=w[i];
            i--;//勿忘！ 
        }    
    }
}
void solve(){
    for(int i=1;i<=n;i++){
        if(pos[i].t) ans+=max(0LL,pos[i].c+pos[i].all-(dp[pos[i].to]-dp[i-1]));    
    }
}
int main(){
    Input();
    BuildDP();
    BuildPos();
    solve();
    cout<<ans<<endl;
}

总结

这么简单一道题，wa了一次，debug了20min，发现是now没赋值，i忘记自减。WTCL！