题目链接
难点是 n 个装置围成了一个环,导致了 DP 的后效性。
解决办法就是在状态中记录两个值(本质就是暴力枚举):
1. 第一个选的设施的位置
2. 因为前面设施的选择,导致从某一个设施往后都不能选。
状态是 $f[i][j][l]$表示前 $i$个设施,第一个选的设施的位置是 $j$,因为前面设施的选择,导致从倒数第 $l$个设施往后都不能选,最大的目标值。
转移的话,对于往前 $k$个,我们暴力转移(因为我们不知道能不能选),对于更前面的,维护一个前缀最小值(肯定可以选)。状态是 $ \Theta (n \cdot k \cdot k) $ 的,转移是 $ \Theta (k) $ 的,总复杂度是 $ \Theta (n\cdot k^3) $ 的,因为有很多状态无效,所以实际上可过。

#include<bits/stdc++.h>
using namespace std;
int dp[1005],n,maxn[1005],val[1005],r[1005],ans;
int max(int a,int b) {
    return a>b?a:b;
}
int min(int a,int b) {
    return a<b?a:b;
}
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>val[i];
        ans=max(ans,val[i]);
    }
    for(int i=1; i<=n; i++)
        cin>>r[i];
    for(int i=1; i<=min(n,50); i++) {
        for(int j=0; j<=min(n,50); j++) {
            if(j+i+r[i]>=n)break;
            else if(r[i]-i+1>j)continue;
            else {
                memset(dp,-1000000000,sizeof(dp));
                dp[i]=val[i];
                memset(maxn,-1000000000,sizeof(maxn));
                maxn[i]=val[i];
                for(int k=i+1; k<=n-j; k++) {
                    if(r[k]-k+1>j)continue;
                    if(k+r[k]-n>=i)continue;
                    else {
                        for(int l=1; l<=min(k-i,50); l++) {
                            if(r[k-l]<l&&r[k]<l)
                                dp[k]=max(dp[k],dp[k-l]+val[k]);
                        }
                        if(k-i>50)
                            dp[k]=max(dp[k],maxn[k-51]+val[k]);
                        maxn[k]=max(maxn[k-1],dp[k]);
                        ans=max(ans,dp[k]);
                    }
                }
            }
        }
    }
    memset(dp,0,sizeof(dp));
    memset(maxn,0,sizeof(maxn));
    dp[51]=val[51];
    maxn[51]=val[51];
    if(n>50)
        for(int k=51; k<=n; k++) {
            for(int l=1; l<=min(k-50,50); l++) {
                if(r[k-l]<l&&r[k]<l)
                    dp[k]=max(dp[k],dp[k-l]+val[k]);
            }
            if(k-50>50)
                dp[k]=max(dp[k],maxn[k-51]+val[k]);
            maxn[k]=max(maxn[k-1],dp[k]);
            ans=max(ans,dp[k]);
        }
    cout<<ans;
    return 0;
}
分类: 文章

darken

华师一退役OIer,QQ:2578050796。 博客园:https://www.cnblogs.com/thedreammaker/

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注