【题解】绝美的挣扎 DP 枚举 洛谷 T44253 -永无岛

题目链接
难点是 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;
}