比赛地址
试题列表
赛题 #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。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include <bits/stdc++.h> #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(){ queue<int>q; 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<<dp[res][0]<<" "<<dp[res][1]<<endl; return 0; } |
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)$ 枚举即可。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// luogu-judger-enable-o2 #include <bits/stdc++.h> #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<<max(ans,f[n][(k<<1)]); } |