题解 P6603 【「EZEC-2」甜梦】

奇米 · 2020-06-15 09:38:02 · 题解

题解 - \mathrm{P6603}\ 甜梦

题目意思

• 题目传送门

\mathrm{Sol}

• 一道很神仙的状压DP

• 我们发现l\leq 12，我们自然而然地想到了状压。于是f_{S,u}表示在状态S下较小的点为u的最大快乐值。S这个东西其实是对[u,u+l]这段区间的二进制表示。

• 我们如何用较小u标号去推出较大标号v，我们首先说出结论v=u+High(S)。其中High(S)为S状态下最高位1的位置。具体是因为我们的DAG是走不了回头路的，所以v一定是当前状态下的最高位。这个还是可以理解的吧。

• 接下来我们来看转移，其实莫过于3种情况。

• [1]$ $u,v$同时移动到$P
  • 那么转移：f_{1,P}=\max(f_{1,P},f_{S,u}+val_{P})
  • 这个好理解就是两个点并到一个点，然后更新状态为1(2^0)
• * 那么转移：$f_{S|(1<<P-u),u}=\max(f_{S|(1<<P-u),u},f_{S,u}+val_P
  • 这个不需要考虑以前状态是否出现过，因为编号是递增的
• * 如果此时$P>v$那么$v$成为较小点，于是$f_{(S>>v-u)|(1<<P-v),v}=\max(f_{(S>>v-u)|(1<<P-v),v},f_{S,u}+val_{P})

  • 此时这个val_P要看在上一个状态中是否出现过

  • 如果此时P<v那么P还是较小点，于是f_{S>>P-u|1,u}=\max(f_{S>>P-u|1,u},f_{S,u}+val_{P})

  • 此时这个val_P要看在上一个状态中是否出现过

• 于是答案就是f_{1,n}。就是两个点都在n点，其他就是写细节问题啦~~~

\mathrm{Code}

#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,b,a) for ( int i=(b);i>=(a);i-- )
#define GO(i,x) for ( int i=head[x];i;i=e[i].nex )
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define YES return puts("YES"),0
#define NO return puts("NO"),0
#define GG return puts("-1"),0
#define pb push_back
using namespace std;

inline int read()
{
    int sum=0,ff=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}

const int mod=1e9+7;
const int mo=998244353;
const int N=5005;
const int M=1<<13|1;

int n,m,l,val[N],a[N][N],f[N][M],High[M];
vector<int> G[N];

int main()
{
    n=read();m=read();l=read();
    For(i,1,n) val[i]=read();
    For(i,1,m)
    {
        int x,y;
        x=read(),y=read();
        if(!a[x][y]) a[x][y]=1,G[x].pb(y);
    }
    For(S,0,(1<<l+1)-1) for ( int j=l+1;~j;j-- ) if((S>>j)&1)
    {
        High[S]=j;
        break;
    }
    memset(f,-1,sizeof(f));
    For(i,1,n)
    {
        if(f[i][1]==-1) f[i][1]=0;
        For(S,0,(1<<l+1)-1)
        {
            if(!(S&1)) continue;
            int idv=i+High[S];
            if(f[i][S]==-1) continue;
            For(j,0,(int)G[idv].size()-1)
            {
                int v=G[idv][j];
                if(a[i][v]) f[v][1]=max(f[i][S]+val[v],f[v][1]);
                if(v-i>l) continue;
                int nxt=S|(1<<v-i);
                f[i][nxt]=max(f[i][nxt],f[i][S]+val[v]);
            }
            For(j,0,(int)G[i].size()-1)
            {
                int v=G[i][j];
                if(v-idv>l) continue;//1:
                if(v>idv)
                {
                    int nxt=(S>>idv-i)|(1<<v-idv);
                    if(S>>v-i&1) f[idv][nxt]=max(f[idv][nxt],f[i][S]);
                    else f[idv][nxt]=max(f[idv][nxt],f[i][S]+val[v]);
                }
                else 
                {
                    int nxt=S>>v-i|1;
                    if(S>>v-i&1) f[v][nxt]=max(f[v][nxt],f[i][S]);
                    else f[v][nxt]=max(f[v][nxt],f[i][S]+val[v]);
                }
            }
        }
    }
    printf("%d\n",f[n][1]);
    return 0;
}