【Luogu Wind Festival!】解题报告

【Luogu Wind Festival!】解题报告

比赛地址

试题列表

赛题 #A:P4741 [Wind Festival]Finding RhFe|满分: 100分
赛题 #B:P4742 [Wind Festival]Running In The Sky|满分: 100分
赛题 #C:P4743 [Wind Festival]Energy Center|满分: 100分
赛题 #D:P4744 [Wind Festival]Iron Man|满分: 100分
难度顺序从小到大:#B #C #D #A

Finding RhFe

Running In The Sky

思路

既然可以“到达一支风筝多次”,也就是可以走回头路,那么我们可以直接 Tarjan 缩点,在新的 DAG 上以拓扑排序的方法 DP。

代码

#include 
#define maxn 500010
using namespace std;
struct Edge{
    int from,to,next;
    Edge(int a=0,int b=0,int c=0){
        from=a,to=b,next=c;
    }
}l[maxn];
struct new_Edge{
    int to,next;
    new_Edge(int a=0,int b=0){
        to=a,next=b;
    }
}e[maxn];
int head[maxn],cnt,n,cnt_n,top,m,ind,dfn[maxn],low[maxn],in[maxn],pin[maxn];
int a[maxn],id[maxn],num,siz[maxn],new_head[maxn],sta[maxn],pma[maxn],vis[maxn];
int dp[maxn][2];
void Add(int x,int y){
    l[++cnt]=Edge(x,y,head[x]);
    head[x]=cnt;
}
void new_Add(int x,int y){
    e[++cnt_n]=new_Edge(y,new_head[x]);
    new_head[x]=cnt_n;
}
void dfs(int u){
    low[u]=dfn[u]=++ind;
    in[u]=1,sta[++top]=u;
    for (int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
        else if (in[v]) low[u]=min(low[u],low[v]);
    }
    if (low[u]==dfn[u]){
        int j=-1;num++;
        while(j!=u){
            j=sta[top--];
            id[j]=num;
            siz[num]+=a[j];
            in[j]=0;
            pma[num]=max(pma[num],a[j]);
        }
    } 
}
void tsort(){
    queueq;
    for (int i=1;i<=n;i++) dp[i][0]=siz[i],dp[i][1]=pma[i];
    //dp[i][0] 维护的是走到 i 的点权和,同时 dp[i][1] 维护路径上的点权最大值。
    for (int i=1;i<=n;i++) if (!pin[i]) q.push(i);
    while(!q.empty()){
        int hq=q.front();q.pop();
        for (int i=new_head[hq];i;i=e[i].next){
            int v=e[i].to;
            if (dp[hq][0]+siz[v]>dp[v][0]){
                dp[v][0]=dp[hq][0]+siz[v];
                dp[v][1]=max(dp[hq][1],pma[v]);//注意这句和下面更新方法的差异
            }
            if (dp[hq][0]+siz[v]==dp[v][0])
                dp[v][1]=max(dp[v][1],dp[hq][1]);
            pin[v]--;if (pin[v]<=0) q.push(v);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=1,t1,t2;i<=m;i++){
        cin>>t1>>t2;Add(t1,t2);
    }
    for (int i=1;i<=n;i++)
        if (!dfn[i]) dfs(i);
    for (int i=1;i<=m;i++)
        if (id[l[i].from]!=id[l[i].to]){
            new_Add(id[l[i].from],id[l[i].to]);
            pin[id[l[i].to]]++;
        }
    int res=1;tsort();
    for (int i=2;i<=num;i++)
        if (dp[i][0]>dp[res][0]||dp[i][0]==dp[res][0]&&dp[i][1]>=dp[res][1]) res=i;
    cout<

Energy Center

Iron Man

思路

看数据范围就知道要写一个 $O(Nk)$ 的 $DP$。 $f[i][2j-2]$ 代表加入了 $a_i$,总共使用了 $j$ 个区间的最大权值和, $f[i][2j-1]$ 代表没加入 $a_i$,总共使用了 $j$ 个区间的最大权值和。对于每一个 $a_i$,转移的时候 $O(k)$ 枚举即可。

代码

// luogu-judger-enable-o2
#include 
#define maxn 200010
#define inf 0x3f3f3f3f
using namespace std;
int n,k,a[maxn],f[maxn][105],ans=-inf;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>a[i];
    memset(f,-inf,sizeof(f));f[0][0]=0;
    for (int i=1;i<=n;i++){
        f[i][0]=max(f[i-1][0],0)+a[i];
        for (int j=1;j<(k<<1);j+=2){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            f[i][j+1]=max(f[i-1][j],f[i-1][j+1])+a[i];
        }
        ans=max(ans,f[i][(k<<1)-2]);
    }
    memset(f,-inf,sizeof(f));f[0][0]=0;
    for (int i=1;i<=n;i++){
        f[i][0]=f[i-1][0]+a[i];
        for (int j=1;j<(k<<1);j+=2){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            f[i][j+1]=max(f[i-1][j],f[i-1][j+1])+a[i];
        }
    }
    cout<