【掘坑記】JZOJ 4707エビソット

テーマの大意
直線上のn個の点で、i番目の点が数軸上の位置x[i]にある.iからjにジャンプすると、まず|x[j]-x[i]|に時間がかかります.iがjより小さい場合は、d[i]+a[j]の追加時間がかかり、i>jの場合はc[i]+b[j]の追加時間がかかる.既に到着した時点では再び到着できません.毎回、いくつかの到達していない点を選択し、そのうちの1つの点から開始し、ある順序ですべての点をスキップし、最終的に開始点にジャンプします.何度かこのような行動をした後、最大どれだけの時間を消費することができますか.(1回の行動から次の行動まで時間を消費しない)n,m<=5000,a[i],b[i],c[i],d[i]<=1 e 9時間制限2 s空間制限256 M
問題を解く構想.
実際には、各ポイントは4つの異なるエッジ状況に基づいて収益を個別に分割し、DPで問題を解決することができます.
f[i][j][k]は、前のi点を選択した後、j個の出度があり、k個の入度が確定していないことを示す.これらの不確定度は,いずれも前i点と後n−i点との間のエッジから生じる.観察したところ、j、kは同時に±1であるため、f[i][j][k]をf[i][j]に変えることができる.状態遷移方程式は以下の通りである:1、f[i+1][j-1]=max(f[i+1][j-1]、f[i][j]+x[i+1]+x[i+1]+a[i+1]+c[i+1]);2、f[i+1][j]=max(f[i+1][j],f[i][j]+a[i+1]+d[i+1]); 3、f[i+1][j]=max(f[i+1][j],f[i][j]+b[i+1]+c[i+1]); 4、f[i+1][j+1]=max(f[i+1][j+1],f[i][j]-x[i+1]-x[i+1]+d[i+1]+b[i+1]); 最初の3つの遷移条件はj>0である.
コードは次のとおりです.

#include
#include
#include
#define maxn 5006
#define fr(i,a,b) for(i=a;i<=b;i++)
using namespace std;
typedef long long ll;

int i,j,n,x[maxn],a[maxn],b[maxn],c[maxn],d[maxn];
ll f[maxn][maxn];
int main()
{
    freopen("mixedblood1.in","r",stdin);
    // freopen("sec.out","w",stdout);
    scanf("%d",&n);
    fr(i,1,n) scanf("%d",&x[i]);
    fr(i,1,n) scanf("%d",&a[i]);
    fr(i,1,n) scanf("%d",&b[i]);
    fr(i,1,n) scanf("%d",&c[i]);
    fr(i,1,n) scanf("%d",&d[i]);

    memset(f,255,sizeof(f));
    f[0][0]=0;
    fr(i,0,n-1)
        fr(j,0,i)
            if (f[i][j]!=-1)
            {
                if (j>0) 
                {
                    f[i+1][j-1]=max(f[i+1][j-1],f[i][j]+x[i+1]+x[i+1]+a[i+1]+c[i+1]);
                    if (i>0)
                    {
                        f[i+1][j]=max(f[i+1][j],f[i][j]+a[i+1]+d[i+1]);
                        f[i+1][j]=max(f[i+1][j],f[i][j]+b[i+1]+c[i+1]);
                    }
                }
                f[i+1][j+1]=max(f[i+1][j+1],f[i][j]-x[i+1]-x[i+1]+d[i+1]+b[i+1]);
            }
    printf("%lld
",f[n][0]);
    return 0;
}