假期计划-暴力出奇迹

· · 个人记录

该题解为另类做法，正解请移步其他题解

家 → 景点 A → 景点 B → 景点 C →景点 D → 家，求途径点权之和的最大值。

看到这样一道题目，很容易能够想到使用朴素的O(4*n)的DP写。

然后再认真一看：“去4个不同的景点”。顿时脑子炸裂。

不过我们仔细一想，因为经过的景点数很少，其实可以dp[i][j][k]记录最大k个值的途径点并进行启发式DP，很难被卡掉。

话不多说，思路简单但码量巨大的代码来咯

#include<bits/stdc++.h>

#define x first
#define y second
#define pf push_front
#define pb push_back

#define rep(i,a,b) for(int i=a;i<(int)(b);i++)
#define r0p(i,n) rep(i,0,n)
#define r1p(i,n) rep(i,1,n+1)
#define all(a) a.begin(),a.end()
#define dbg(a) cerr<<#a<<": "<<a<<endl
#define sz(a) (int)(a.size())
#define re(a) cout<<a<<endl,exit(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int intmx=0x3f3f3f3f;
const ll llmx=LLONG_MAX-10000ll*INT_MAX;

template <typename T> inline T abs(T a){return a<0?-a:a;}

void IO(string s=""){
    if(!sz(s)) return;
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

#define N 2505
#define M 10005
#define L 10//此处最好开大一点，防止别卡。（虽然实测开成4就能过）

int n,m,k;
ll v[N]={0};
ll dp[N][6][L][6]={0};//dp[i][e][l]表示走e步到i后点权和第l大的路径方案，dp[i][e][l][0]表示路径方案的点权和，dp[i][e][l][tmp](tmp>0)表示该路径方案途径的第tmp个点
vector<int>b[N];
vector<int>a[N];
bool ok[N][N]={0};
queue<pair<int,int> >q;

inline void upd(int i,int e,int lev){
    if(lev!=-1&&dp[i][e][lev][0]<dp[i][e][lev+1][0]){
        for(int tmp=0;tmp<=e;tmp++) swap(dp[i][e][lev+1][tmp],dp[i][e][lev][tmp]);
        upd(i,e,lev-1);
    }
}//更新后将dp[i][e]手动冒泡排序

inline bool conf(int i,int j,int e,int l){
    for(int tmp=1;tmp<=e;tmp++) if(j==dp[i][e][l][tmp]) return 1;
    return 0;
}//即将经过的点与之前的点不冲突

signed main(){
    scanf("%d%d%d",&n,&m,&k);
    rep(i,2,n+1) scanf("%lld",&v[i]);
    r0p(i,m){
        int u,vv;
        scanf("%d%d",&u,&vv);
        b[u].pb(vv);
        b[vv].pb(u);
    }
    r1p(i,n){
        //建图
        q.push({i,-1});
        ok[i][i]=1;
        while(!q.empty()){
            int j=q.front().x,val=q.front().y;
            q.pop();
            if(val==k) continue;
            for(auto l:b[j]) if(!ok[i][l]){
                ok[i][l]=1;
                a[i].pb(l);
                q.push({l,val+1});
            }
        }
        //初始化dp值
        r0p(e,6) r0p(l,L) dp[i][e][l][0]=-1;
    }
    dp[1][0][0][0]=0;
    r0p(e,5){//刷表法
        r1p(i,n) r0p(l,L) if(dp[i][e][l][0]>=0){//该路径方案存在
            for(auto j:a[i]) if(e==4?j==1:!conf(i,j,e,l)&&dp[j][e+1][L-1][0]<dp[i][e][l][0]+v[j]){//不与之前的点冲突且点权和大于当前倒一（值得被更新）
                //更新倒一
                dp[j][e+1][L-1][0]=dp[i][e][l][0]+v[j];
                for(int tmp=1;tmp<=e;tmp++) dp[j][e+1][L-1][tmp]=dp[i][e][l][tmp];
                dp[j][e+1][L-1][e+1]=j;
                //向前冒泡
                upd(j,e+1,L-2);
            }
        }
    }
    printf("%lld\n",dp[1][5][0][0]);
    exit(0);
}