比赛地址
试题列表
赛题 #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<