daily 2

CF 1132F

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    s=')'+s;
    vector dp(n+1,vector<ll>(n+1));
    for(int len=1;len<=n;++len){
        for(int l=1;l+len-1<=n;++l){
            int r=l+len-1;
            if(r==l){
                dp[l][r]=1;
                continue;
            }
            ll cur_best=INF;
            for(int k=l;k<r;++k){
                if(s[k]==s[r]){
                    cur_best=min(cur_best,dp[l][k]+dp[k+1][r-1]);
                }else{
                    cur_best=min(cur_best,dp[l][k]+dp[k+1][r-1]+1);
                }
            }
            dp[l][r]=cur_best;
        }
    }
    cout<<dp[1][n]<<'\n';
}

CF 1155D

int main(){
    ll n,x;
    cin>>n>>x;
    vector<int>a(n+1);
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    vector dp(n+1,vector<ll>(3));
    ll ans=0;
    for(int i=1;i<=n;++i){
        dp[i][0]=max(dp[i-1][0]+a[i],0ll);//不做
        dp[i][1]=max(dp[i][0],dp[i-1][1]+a[i]*x);//正在做
        dp[i][2]=max(dp[i][1],dp[i-1][2]+a[i]);//刚做完
        ans=max(ans,dp[i][2]);
    }
    cout<<ans<<'\n';
}