「巴蜀中学NOIP2017模拟D3T3」大逃杀 - 树上背包 | Bill Yang's Blog

「巴蜀中学NOIP2017模拟D3T3」大逃杀 - 树上背包

题目大意

    自从Y君退役之后,她就迷上了吃鸡,于是她决定出一道吃鸡的题。
    Y君将地图上的所有地点标号为$1$到$n$,地图中有$n-1$条双向道路连接这些点,通过一条双向道路需要一定时间,保证从任意一个点可以通过道路到达地图上的所有点。
    有些点上可能有资源,Y君到达一个有资源的点后,可以选择获取资源来使自己的武力值增加$w_i$,也可以选择不获取资源。如果Y君获取了一个点上的资源,这个点上的资源就会消失,获取资源不需要时间。
    有些点上可能有敌人,Y君到达一个有敌人的点后,必须花费$t_i$秒伏地与敌人周旋,并最终将敌人消灭。如果Y君消灭了一个点上的敌人,这个点上的敌人就会消失。Y君不能无视敌人继续前进,因为这样会被敌人攻击。
    如果一个点上既有资源又有敌人,Y君必须先消灭敌人之后才能获取资源,否则就会被敌人突袭。
    游戏开始时,Y君可以空降到任意一个点上,接下来,她有$T$秒进行行动,$T$秒后她就必须前往中心区域送快递。Y君希望她前往中心区域送快递时,武力值尽可能大,请你帮助Y君设计路线,以满足她的要求。你只需输出$T$秒后Y君的武力值。


题目分析

很像 收稻子和「CQOI2017」小Q的棋盘 这两道题。
但是因为没有指定根,因此需要枚举根,时间复杂度$O(n^4)$,随机化卡卡时,在考试中得到了65分。

实际上正解已经很接近了。
我们考虑不枚举根,通过背包分配时间来限制其移动。

不难发现,实际上经过一个点我们这几种经过方式:

那么不妨设置状态$f[i,j,0/1/2]$表示$i$结点的子树需要分配$j$的时间,第三维表示引申出去几条单链 所得到的最大武力值。

  • 转移1:环环
    其中的$j$表示当前分配的时间,$p$表示给$v$分配的时间。
  • 转移2:环边
  • 转移3:边环
  • 转移4:环链
  • 转移5:链环
  • 转移6:链链

注意因为边权有$0$,所以不能直接使用$f$数组循环赋值,需要开一个$tmp$数组分离以前状态和当前状态。


代码

暴力65分

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int max(const int& a,const int& b) {
if(a>b)return a;
return b;
}
struct Edge {
int from,to,dist;
};
vector<Edge>edges[305];
void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {
x,y,v
});
}
int n,k,a[305],t[305],tmp[305],f[305][305][2],ans=0;
int xyj=0;
const int rp=89995999;
void TreeDp(int Now,int father) {
for(int i=0; i<=k; i++)f[Now][i][0]=f[Now][i][1]=0;
for(int i=0; i<edges[Now].size(); i++) {
Edge& e=edges[Now][i];
int Next=e.to;
if(Next==father)continue;
TreeDp(Next,Now);
for(int j=k; j>=0; j--)
for(int p=0; p<=j-t[Next]-e.dist; p++) {
xyj++;
if(j-p>=2*e.dist+t[Next])f[Now][j][0]=max(f[Now][j][0],f[Next][p][0]+f[Now][j-p-t[Next]-2*e.dist][0]);
f[Now][j][1]=max(f[Now][j][1],f[Next][p][1]+f[Now][j-p-t[Next]-e.dist][0]);
if(j-p>=2*e.dist+t[Next])f[Now][j][1]=max(f[Now][j][1],f[Next][p][0]+f[Now][j-p-t[Next]-2*e.dist][1]);
}
}
for(int i=0; i<=k; i++) {
xyj++;
f[Now][i][0]+=a[Now];
f[Now][i][1]+=a[Now];
}
}
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int(),tmp[i]=i;
for(int i=1; i<=n; i++)t[i]=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
AddEdge(y,x,v);
}
random_shuffle(tmp+1,tmp+n+1);
for(int i=1; i<=n; i++) {
int x=tmp[i];
k-=t[x];
TreeDp(x,0);
for(int j=0; j<=k; j++)ans=max(ans,f[x][j][1]);
k+=t[x];
if(xyj>rp)break;
}
printf("%d\n",ans);
return 0;
}

正解100分

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=305;
struct Edge {
int from,to,dist;
};
vector<Edge>edges[maxn];
void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {
x,y,v
});
}
int n,T,t[maxn],a[maxn],f[maxn][maxn][3],tmp[maxn][3],ans=0;
void TreeDp(int Now,int father) {
for(int i=t[Now]; i<=T; i++)f[Now][i][0]=f[Now][i][1]=f[Now][i][2]=0;
for(int i=0; i<edges[Now].size(); i++) {
Edge& e=edges[Now][i];
int Next=e.to;
if(Next==father)continue;
TreeDp(Next,Now);
memcpy(tmp,f[Now],sizeof(f[Now]));
for(int j=T; j>=0; j--)
for(int p=0; p<=j-e.dist; p++) {
if(j-p>=2*e.dist) {
f[Now][j][0]=max(f[Now][j][0],tmp[j-p-2*e.dist][0]+f[Next][p][0]);
f[Now][j][1]=max(f[Now][j][1],tmp[j-p-2*e.dist][1]+f[Next][p][0]);
f[Now][j][2]=max(f[Now][j][2],tmp[j-p-2*e.dist][0]+f[Next][p][2]);
f[Now][j][2]=max(f[Now][j][2],tmp[j-p-2*e.dist][2]+f[Next][p][0]);
}
f[Now][j][1]=max(f[Now][j][1],tmp[j-p-e.dist][0]+f[Next][p][1]);
f[Now][j][2]=max(f[Now][j][2],tmp[j-p-e.dist][1]+f[Next][p][1]);
}
}
for(int i=t[Now]; i<=T; i++) {
f[Now][i][0]+=a[Now];
f[Now][i][1]+=a[Now];
f[Now][i][2]+=a[Now];
ans=max(ans,max(f[Now][i][0],max(f[Now][i][1],f[Now][i][2])));
}
}
int main() {
n=Get_Int();
T=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=n; i++)t[i]=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
AddEdge(y,x,v);
}
for(int i=1; i<=n; i++)
for(int j=0; j<=T; j++)
f[i][j][0]=f[i][j][1]=f[i][j][2]=-0x7fffffff/2;
TreeDp(1,0);
printf("%d\n",ans);
return 0;
}

本篇文章有用吗?有用还不快点击!
0%